数据结构：图(Graph)【详解】

友情链接：数据结构专栏

在线性表中，数据元素之间是被串起来的，仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关。图是一种较线性表和树更加复杂的数据结构。在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

图(Graph)是由顶点的有穷非空集合 V ( G ) V(G) V(G)和顶点之间边的集合 E ( G ) E(G) E(G)组成，通常表示为: G = ( V , E ) G=(V,E) G=(V,E)，其中， G G G表示个图， V V V是图 G G G中顶点的集合， E E E是图 G G G中边的集合。若 V = { v 1 , v 2 , . . . , v n } V= \{v_1, v_2,...,v_n\} V={v1​,v2​,...,vn​}，则用 ∣ V ∣ |V| ∣V∣表示图 G G G中顶点的个数，也称图 G G G的阶， E = { ( u , v ) ∣ u ∈ V , v ∈ V } E= \{(u, v) |u∈V, v∈V\} E={(u,v)∣u∈V,v∈V}，用 ∣ E ∣ |E| ∣E∣表示图 G G G中边的条数。

注意:线性表可以是空表，树可以是空树，但图不可以是空图。就是说，图中不能一个顶点也没有，图的顶点集V一定非空，但边集E可以为空，此时图中只有顶点而没有边。

若E是有向边(也称弧)的有限集合时，则图G为有向图。弧是顶点的有序对，记为，其中v,w是顶点，v称为弧尾，w称为弧头，称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接自v。 图(a)所示的有向图 G 1 G_1 G1​可表示为 G 1 = ( V 1 , E 1 ) G_1 = (V_1,E_1) G1​=(V1​,E1​) V 1 = { 1 , 2 , 3 } V_1=\{1,2,3\} V1​={1,2,3} E 1 = { < 1 , 2 > , < 2 , 1 > , < 2 , 3 > } E_1=\{,,\} E1​={,,}

若E是无向边(简称边)的有限集合时，则图G为无向图。边是顶点的无序对，记为(v, w)或(w,v),因为(v,w)=(w,v), 其中v,w是顶点。可以说顶点w和顶点v互为邻接点。边(v, w)依附于顶点w和v，或者说边(v, w)和顶点v, w相关联。

图(b)所示的无向图G2可表示为 G 2 = ( V 2 , E 2 ) G_2=(V_2,E_2) G2​=(V2​,E2​) V 2 = { 1 , 2 , 3 , 4 } V_2=\{1,2,3,4\} V2​={1,2,3,4} E 2 = { ( 1 , 2 ) , ( 1 , 3 ) , ( 1 , 4 ) , ( 2 , 3 ) , ( 2 , 4 ) , ( 3 , 4 ) } E_2=\{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\} E2​={(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)}

一个图 G G G若满足:①不存在重复边;②不存在顶点到自身的边，则称图 G G G为简单图。上图中 G 1 G_1 G1​和 G 2 G_2 G2​均为简单图。数据结构中仅讨论简单图。

若图 G G G中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G G G为多重图。多重图的定义和简单图是相对的。

对于无向图， ∣ E ∣ |E| ∣E∣的取值范围是 0 0 0到 n ( n − 1 ) / 2 n(n-1)/2 n(n−1)/2，有 n ( n − 1 ) / 2 n(n -1)/2 n(n−1)/2条边的无向图称为完全图，在完全图中任意两个顶点之间都存在边。对于有向图， ∣ E ∣ |E| ∣E∣的取值范围是 0 0 0到 n ( n − 1 ) n(n-1) n(n−1)，有 n ( n − 1 ) n(n-1) n(n−1)条弧的有向图称为有向完全图，在有向完全图中任意两个顶点之间都存在方向相反的两条弧。上图中 G 2 G_2 G2​为无向完全图，而 G 3 G_3 G3​为有向完全图。

设有两个图 G = ( V , E ) G=(V, E) G=(V,E)和 G ′ = ( V ′ , E ′ ) G'=(V', E') G′=(V′,E′)， 若 V ′ V' V′是 V V V的子集，且 E ′ E' E′是 E E E的子集，则称 G ′ G' G′是 G G G的子图。若有满足 V ( G ′ ) = V ( G ) V(G')= V(G) V(G′)=V(G)的子图 G ′ G' G′，则称其为 G G G的生成子图。上图中 G 3 G_3 G3​为 G 1 G_1 G1​的子图。

注意:并非V和E的任何子集都能构成G的子图，因为这样的子集可能不是图，即E的子集中的某些边关联的顶点可能不在这个V的子集中。

在无向图中，若从顶点 v v v到顶点 w w w有路径存在，则称 v v v和 w w w是连通的。若图 G G G中任意两个顶点都是连通的，则称图 G G G为连通图，否则称为非连通图。无向图中的极大连通子图称为连通分量。若一个图有 n n n个顶点，并且边数小于 n − 1 n-1 n−1，则此图必是非连通图。如下图(a)所示， 图 G 4 G_4 G4​有3个连通分量，如图（b）所示。

注意:弄清连通、连通图、连通分量的概念非常重要。首先要区分极大连通子图和极小连通子图，极大连通子图是无向图的连通分量，极大即要求该连通子图包含其所有的边;极小连通子图是既要保持图连通又要使得边数最少的子图。

在有向图中，若从顶点 v v v到顶点 w w w和从顶点 w w w到项点 v v v之间都有路径,则称这两个顶点是强连通的。若图中任何一对顶点都是强连通的，则称此图为强连通图。有向图中的极大强连通子图称为有向图的强连通分量，图 G 1 G_1 G1​的强连通分量如下图所示。

注意:强连通图、强连通分量只是针对有向图而言的。一般在无向图中讨论连通性，在有向图中考虑强连通性。

连通图的生成树是包含图中全部顶点的一个极小连通子图。若图中顶点数为 n n n,则它的生成树含有 n − 1 n-1 n−1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。在非连通图中，连通分量的生成树构成了非连通图的生成森林。图 G 2 G_2 G2​的一个生成树如下图所示。

注意:包含无向图中全部顶点的极小连通子图，只有生成树满足条件，因为砍去生成树的任一条边，图将不再连通。

图中每个顶点的度定义为以该项点为一个端点的边的数目。 对于无向图，顶点v的度是指依附于该顶点的边的条数，记为 T D ( v ) TD(v) TD(v)。 在具有 n n n个顶点、 e e e条边的无向图中， ∑ i = 1 n T D ( v i ) = 2 e \displaystyle\sum_{i=1}^{n}TD(v_i)= 2e i=1∑n​TD(vi​)=2e，即无向图的全部顶点的度的和等于边数的2倍，因为每条边和两个顶点相关联。 对于有向图,顶点 v v v的度分为入度和出度,入度是以顶点 v v v为终点的有向边的数目，记为 I D ( v ) ID(v) ID(v); 而出度是以顶点 v v v为起点的有向边的数目，记为 O D ( v ) OD(v) OD(v)。顶点 v v v的度等于其入度和出度之和，即 T D ( v ) = I D ( v ) + O D ( v ) 。 TD(v) = ID(v) + OD(v)。 TD(v)=ID(v)+OD(v)。 在具有 n n n个顶点、 e e e条边的有向图中， ∑ i = 1 n I D ( v i ) = ∑ i = 1 n O D ( v i ) = e \displaystyle\sum_{i=1}^{n}ID(v_i)=\displaystyle\sum_{i=1}^{n}OD(v_i)=e i=1∑n​ID(vi​)=i=1∑n​OD(vi​)=e，即有向图的全部顶点的入度之和与出度之和相等，并且等于边数。这是因为每条有向边都有一个起点和终点。

在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。这种边上带有权值的图称为带权图，也称网。

边数很少的图称为稀疏图，反之称为稠密图。稀疏和稠密本身是模糊的概念，稀疏图和稠密图常常是相对而言的。一般当图G满足 ∣ E ∣ < ∣ V ∣ l o g ∣ V ∣ |E| < |V|log|V| ∣E∣=0; w=NextNeighor(G, v, w)){ if(!visited[w]){ //w为u的尚未访问的邻接顶点 DFS(G, w); } } } /*对图进行深度优先遍历*/ void DFSTraverse(MGraph G){ int v; for(v=0; v A 1 [ 1 ] [ 2 ] + A 1 [ 2 ] [ 0 ] = 9 A^{1}[1][0] > A^{1}[1][2] + A^{1}[2][0] = 9 A1[1][0]>A1[1][2]+A1[2][0]=9，更新后的方阵标记为 A 2 A^2 A2。此时 A 2 A^2 A2中保存的就是任意顶点对的最短路径长度。

应用Floyd算法求所有顶点之间的最短路径长度的过程如下表所示。 从这个表中，可以发下一些规律： 可以看出，矩阵中，每一步中红线划掉的部分都不用考虑计算，只需要计算红线外的部分，节省了计算量。

Floyd算法的时间复杂度为 O ( V 3 ) O(V^3) O(V3)。不过由于其代码很紧凑，且并不包含 其他复杂的数据结构，因此隐含的常数系数是很小的，即使对于中等规模的输入来说，它仍然是相当有效的。 Floyd算法允许图中有带负权值的边，但不允许有包含带负权值的边组成的回路。Floyd 算法同样适用于带权无向图，因为带权无向图可视为权值相同往返二重边的有向图。 也可以用单源最短路径算法来解决每对顶点之间的最短路径问题。轮流将每个顶点作为源点，并且在所有边权值均非负时，运行一次 Dijkstra算法，其时间复杂度为 O ( V 3 ) ∗ V = O ( V 3 ) O(V^3)*V = O(V^3) O(V3)∗V=O(V3)。

在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网( Activity On VertexNetwork)。 若用DAG图（有向无环图）表示一个工程，其顶点表示活动，用有向边 < V i , V j > 表示活动 V i V_i Vi​必须先于活动 V j V_j Vj​进行的这样一种关系。在AOV网中，活动 V i V_i Vi​是活动 V j V_j Vj​的直接前驱，活动 V j V_j Vj​是活动 V i V_i Vi​的直接后继，这种前驱和后继关系具有传递性，且任何活动 V i V_i Vi​不能以它自己作为自己的前驱或后继。 设 G = ( V , E ) G=(V,E) G=(V,E)是一个具有n个顶点的有向图， V V V中的顶点序列 V 1 , V 2 , . . . V n V_1, V_2, ... V_n V1​,V2​,...Vn​，满足若从顶点 V i V_i Vi​到 V j V_j Vj​有一条路径，则在顶点序列中顶点 V i V_i Vi​必在顶点 V j V_j Vj​之前。则我们称这样的顶点序列为一个拓扑序列。

所谓拓扑排序，其实就是对一个有向图构造拓扑序列的过程。每个AOV网都有一个或多个拓扑排序序列。

对一个AOV网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤:

上图所示为拓扑排序过程的示例。每一轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为 { 1 , 2 , 4 , 3 , 5 } \{1,2, 4, 3,5\} {1,2,4,3,5}。 拓扑排序算法的实现如下：