图

图$G$由顶点（数据元素）集$V$和边集（顶点之间的关系）$E$组成，即为$G=(V,E)$。若$V={v_1,v_2,…,v_n}$，则用$|V|$表示图中的顶点个数，$E={(u,v)|u \in V,v \in V}$。顶点集$V$必须是非空集合。

基本术语

• 有向图：$(u,v)$和$(v,u)$被视作同一条边，其中$u \in V, v \in V$。
• 无向图：$(u,v)$和$(v,u)$是两条不同的边，其中$u \in V, v \in V$。
• 相邻(Adjacent)：边$(u,v)$连接的顶点$u$和$v$相邻。相邻是顶点和顶点间的关系。
• 关联(Incident)：边$(u,v)$和其连接的顶点$u$（或$v$）相互关联。
• 简单图：不存在重复边和自环的图。
• 完全图：任意两个点之间都存在边。
  • 无向图的完全图：有$n(n-1)/2$条边的无向图。
  • 有向图的完全图：有$n(n-1)$条边的有向图。
• 子图：设两个图$G=(V,E)$和$G’=(V’,E’)$，若$V’$是$V$的子集，$E’$是$E$的子集，则称$G’$是$G$的子图。若满足$V(G’)=v(G)$，则称$G’$是$G$的生成子图。
• 顶点的度(Degree of a Vertex)：顶点$u$的度$deg(u)$是和$u$关联的边的数量。
• 图的度：图各顶点的度之和，即$deg(G)=\sum_{v \in V}deg(v)$。和树的度定义不一样。
• 握手定理(Handshaking Lemma)：无向图的度是边数的两倍，即$deg(G)=2|E|$。
• 路径(Path)：顶点$vp$到顶点$v_p$之间的路径是指顶点序列$<v_p,v{i1},v{i2},…,v{im},v_q>$。存在路径$<v_p,v{i1},v{i2},…,v{i_m},v_q>$，说明$v_p$可达$v_q$。
• 路径长度：路径上的边的数量。
• 回路：第一个顶点和最后一个顶点相同的路径。若一个图有$n$个顶点，且有大于$n-1$条边，则图中一定有环。
• 简单路径：顶点不重复出现的路径。
• 简单回路：除了第一个顶点和最后一个顶点，其余顶点不重复出现的回路。
• 连通、连通图和连通分量：针对无向图的概念。
  • 若顶点$v$到顶点$u$有路径存在，则称$v$和$u$是连通的。
  • 若图$G$中任意两个顶点都是相通的，则称图$G$是连通图。
  • 连通分量(Connected Components)：根据是否连通将顶点进行分组，相互可达的顶点集和对应的边集称为连通分量。
  • 极小连通子图：子图连通，且包含最少的边。
  • 极大连通子图：子图连通，且包含最多的边。
  • 无向图中的极大连通子图称为极大连通分量。
• 强连通、强连通图和强连通分量：针对有向图的概念。
  • 若一对顶点$v$和$u$，从$v$到$u$和从$u$到$v$之间都有路径，则称这两个顶点是强连通的。
  • 若图中任意一对顶点都是强连通的，则称此图为强连通图。
  • 有向图中的极大强连通子图称为图的强连通分量。
  • 极小强连通子图：子图强连通，包含最少的边。
  • 极大强连通子图：子图强连通连通，包含最多的边。
• 生成树：连通图（说明是无向图）的生成树是包含图中全部顶点的一个极小连通子图。若图中有$n$个结点，则它的生成树有$n-1$条边。
• 生成森林：在非连通图中，连通分量的生成树构成了非连通图的生成森林。
• 距离：从顶点$v$到顶点$u$存在的最短路径。
• 树：_向图在什么条件下成为了树。连通、无环图是树$T=$，树有$|V_T|-1$条边。

图的存储

逻辑结构——图，在计算机物理内存内如何存储。如何在计算机内存中存储图里数据元素之间的逻辑关系。

需要思考的点：为什么有这种存储方式？每个存储方式的优势和劣势，以及使用场景。

邻接矩阵法

使用一个一维数组存储图中顶点信息；使用一个二维数组存储图中边的信息（各顶点间的邻接关系），存储边信息的二维数组称为邻接矩阵。

顶点数为$n$的图$G=$的邻接矩阵A是$n \times n$的，将顶点集$G$中的顶点编号是$v_1,v_2,…,v_n$，则：

$$A[i][j] = \begin{cases} 0, & (v_i,v_j)\ or <v_i,v_j> is\ an\ edge \\ 1, & (v_j,v_i)\ or <v_j,v_i> is\ an\ edge \end{cases}$$

在带权图，如果顶点$v_i$和$v_i$之间没有边，则$A[i][j]=A[j][i]=\infty$，如果有边，那么$A[i][j]$或者$A[j][i]$的值是边的权值。

邻接矩阵法存储空间复杂度：$O(n^2)$，其中$n=|V|$。

缺点：当图是稀疏图时，邻接矩阵法会浪费大量存储空间。

邻接表法

邻接表法结合了顺序存储和链式存储方法。

边表：对图$G$中的每个顶点$v_i$建立一个单链表，第$i$个单链表中的结点表示从顶点$v_i$出发的边（对于无向图是和$v_i$关联的边）。边表结点包含两个域，邻接点域（存储和顶点$v_i$邻接的顶点编号），和指向下一条边的边表结点的指针。

顶点表：指向边表的指针和顶点的数据信息采用顺序存储，称为顶点表。顶点表的顶点结点包含两个域，指向边表的指针域，和保存顶点$v_i$信息的顶点域。

有向图邻接表法的空间复杂度是$O(|V|+|E|)$，无向图邻接表法的空间复杂度是$O(|V|+2|E|)$。

邻接矩阵法和邻接表法的优缺点对比

• 邻接表法更适合稀疏图的存储。
• 邻接表法适合查找某个顶点关联的所有边，相同的操作在邻接矩阵法中需要$O(|V|)$的时间复杂度。
• 邻接矩阵法适合判断两个顶点之间是否存在边，操作的时间复杂度是$O(1)$，而在邻接表法中需要遍历顶点的边集。
• 在求顶点的度操作中，邻接链表比邻接矩阵法效率更高。

十字链表

十字链表是有向图的一种链式存储结构，使用弧结点表示弧（有向图的边），使用顶点结点表示顶点。

弧结点：
|弧尾结点|弧头结点|弧头相同的下一个弧结点的指针|弧尾相同的下一个弧结点的指针|弧的信息|
|————|———|———|———|———|
|$tail_vertex$|$head_vertex$|$tail_link$|$head_link$|$Info$ |

顶点结点：
| 顶点数据信息 |指向以该顶点为弧头的第一个弧结点| 指向以该顶点为弧尾的第一个弧结点|
|————|———|———|
|$data$|$first_in_edge$|$first_out_edge$|

由于有$|V|$个顶点结点，有$|E|$个弧结点，所以空间复杂度是$O(|V|+|E|)$。

邻接多重表

邻接多重表是无向图的一种链式存储结构。每条边都用一个结点表示，每个顶点用一个结点表示。

边结点：
|结点1|下一条依附于结点1的边结点的指针|结点2|下一条依附于结点2的边结点的指针|边的信息|
|————|———|———|———|———|
|$vertex_1$|$link_1$|$vertex_2$|$link$_2|$Info$ |

顶点结点：

由于有$|V|$个顶点结点，有$|E|$个边结点，所以空间复杂度是$O(|V|+|E|)$。

几种存储方法对比

---

• ← Previous Post
• Next Post →