图模型:图数据结构

一、概念

参考：https://blog.csdn.net/qq_35644234/article/details/57083107

图的定义

• 图（Graph）是描述实体（entity）和关系（relation）的一种通用语言形式，它由节点（Vertex或node）和连接节点的边（Edge或link）组成，很多数据模型都可以用图的形式来描述。
• 图由节点的有穷非空集合和节点之间边的集合组成，通常表示为：\(G(V,E)\)，其中，\(G\)表示一个图，\(V\)是图\(G\)中节点的集合，\(E\)是图\(G\)中边的集合。

图的种类

• 图按照边的有无方向分为无向图和有向图。

  • 无向图由节点和边组成；
  • 有向图由节点和弧组成，弧有弧尾和弧头之分，带箭头一端称为弧头；

• 图按照边或弧的多少分为稀疏图和稠密图，是个相对概念，只有在对比时才有其意义，可以用全局聚类系数来量化对比。下面的类型是绝对概念：

  • 如果图中的任意两个节点之间都存在边，则称为完全图，有向的称为有向完全图；
  • 如果没有重复的边且没有节点到其自身的边则称为简单图，简单图是我们最常用的；

• 图上的边或弧带有权，则称为网（Network）。

• 如果有两个图 \(G = (V, E)\)，\(G' = (V', E')\)，满足\(V' \subseteq V\)，\(E' \subseteq E\)，那么，称\(G'\)是\(G\)的子图。

• 对于无向图，如果满足图中任意两个节点都存在路径（路径中间存在其他节点，也称为存在路径），则称为连通图（Connected Graph）。

• 无向图中的极大连通子图称为该无向图的联通分量（Giant Component），满足以下几点：

  • 需要是该无向图的子图；
  • 该子图是连通图；
  • 该子图在所属的连通图中具有极大节点数；
  • 该子图需要包含依附于这些节点的所有边；

图的性质

• 图中节点之间有邻接点、依附的概念。
• 无向图节点u的边数叫做该节点的度\(k_u\)，无向图中所有节点的平均度 avg(k) = 2*E/V。有向图节点分为入度和出度。
• 图不是欧几里得数据结构，没有固定的大小和拓扑结构。
• 图上的节点没有固定的顺序，也没有参考点，是去中心化的。
• 图会随着时间动态变化，并且图中常常会融合多模态信息。
• 节点的度分布（degree distribution）\(P(k) = N_k / N\)，示例（横坐标为度k，纵坐标为度为k的节点占比）：
  • 【补图】
• 聚类系数（Clustering Coefficient）
  • 局部聚类系数
    • 含义：
      • 描述一个无向图中的某节点与其邻节点之间聚集成团的程度的一个系数。
      • 一个节点的聚类系数体现的是其邻节点也相互连通的可能性，即一阶邻节点之间有边的概率，对应到社交网络，可以理解为我的朋友之间相互认识的程度。
      • 一个节点的聚类系数被称为局部聚类系数。
    • 计算：
      • 节点u的聚类系数 = 节点u与邻节点实际构成的三角形数除以最大可能的三角形数，或者说 邻节点之间实际所连的边的数量除以这些节点之间可以连出的最大边数，即\(CC(u) = \frac{2R_u}{k_u(k_u-1)}\)。
      • 其中\(k_u\)为节点u的度，或者u的一阶邻节点数；
      • 邻节点之间可以连出的最大边数为\(\frac{k_u(k_u-1)}{2}\)，即邻接点构成的完全图的边数；
      • 邻节点之间实际所连的边为\(R_u\)，可以通过该子图（节点u与邻节点组成的子图）的所有边数减去\(k_u\)得到；
    • 小世界网络：https://zh.m.wikipedia.org/zh-hans/%E5%B0%8F%E4%B8%96%E7%95%8C%E7%B6%B2%E8%B7%AF
  • 全局聚类系数
• 生成树：
  • 无向图中连通且n个节点n-1条边称为生成树。有向图中一节点入度为0其余节点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。
• TODO：生成树。

二、存储结构

邻接矩阵

邻接矩阵的表示方式用两个数组来表示图的信息，一个一维数组表示每个数据元素的信息，一个二维数组（邻接矩阵）表示图中的边或者弧的信息。

优点：

• 直观、容易理解，可以很容易的判断出任意两个节点之间是否有边，最大的优点就是很容易计算出各个顶点的度。

缺点：

• 当需要表示完全图的时候，邻接矩阵是最好的表示方法，但是对于稀疏矩阵，由于它边少，但是顶点多，这样就会造成空间的浪费。

邻接表

将数组和链表结合。主要是应对邻接矩阵在顶点多边少的时候，空间浪费的问题。

节点通过一个头结点类型的一维数组来保存，每个节点的所有邻接点组成一个链表后缀在其头结点上。

具体来说，其中每个头结点的firstarc都是指向一条依附在该节点的边的信息（表结点），表结点的adjvex表示该边的另外一个节点在一维数组中的下标，weight用于存储边的权重，nextarc指向的是下一条依附在该节点的边的信息。

优点：

• 对于稀疏图，邻接表比邻接矩阵更节约空间。
• 计算节点的出度容易，即一个头结点后缀的链长度。

缺点：

• 不容易判断出任意两个节点之间是否有边。
• 求任一一个节点的入度都需要遍历整个邻接表。

十字链表

有向图的一个专有的链表结构，用于解决节点入度计算难的问题。

邻接多重表

三、相关算法

图的遍历

从图中某一个顶点出发遍访图的其余所有顶点，且使所有顶点被访问且只访问一次。这个过程，就叫做图的遍历（Traversing Graph）。

深度优先遍历Depth_First_Search

广度优先遍历Breadth_First_Search

最小生成树

把构造连通网的最小代价生成树称为最小生成树（Minimum Cost Spanning Tree）。

普里姆(Prim)算法

克鲁斯卡尔（Kruskal）算法

最短路径

非网图的最短路径，是指两顶点之间经过的边数最少的路径。网图的最短路径，是指两顶点之间经过的边上的权值之和最小的路径。路径上的第一个源点，最后一个顶点是终点。

拓扑排序

关键路径

折叠文本说明