1.3 图

在线性结构（例如队列和栈）中，除第一个结点没有前驱，最后一个结点没有后继之外，每一个结点都有唯一的一个前驱和后继。在树形结构（例如树和二叉树）中，除根结点没有前驱外，一个结点只有一个前驱结点，但可以有若干个后继。在图结构中，一个结点的前驱和后继的个数都是任意的。

1.3.1 图的基础知识

1．图的基本概念

图 G 由两个集合 V 和 E 组成，记为 G =( V ， E )，其中 V 是顶点的有穷非空集合， E 是 V 中顶点偶对（称为边）的有穷集合。通常，也将图 G 的顶点集和边集分别记为 V ( G )和 E ( G )。 E ( G )可以是空集。若 E ( G )为空，则图 G 只有顶点而没有边。

图分为有向图和无向图两种。图1-11（a）是一个有向图，在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。＜V i ，V j ＞表示一条有向边，V i 是边的始点（起点），Vj是边的终点，＜V i ，V j ＞和＜V j ，V i ＞是两条不同的有向边。例如，在图1-11（a）中，＜V1，V4＞和＜V4，V1＞是两条不同的边。有向边也称为弧，边的始点称为弧尾，终点称为弧头。

图1-11（b）是一个无向图，无向图中的边均是顶点的无序对，无序对通常用圆括号表示。在无向图 G 中，如果 i ≠ j ， i 、 j ∈ V ，( i ， j )∈ E ，即 i 和 j 是 G 的两个不同的顶点，（ i ， j ）是 G 中一条边，顶点 i 和顶点 j 是相邻顶点，边（ i ， j ）是与顶点 i 和 j 相关联的边。

如果限定任何一条边或弧的两个顶点都不相同，则有 n 个顶点的无向图至多有 n ( n –1)/2条边，这样的无向图称为无向完全图。一个有向图至多有 n ( n –1)条弧，这样的有向图称为有向完全图。

如果同为无向图或同为有向图的两个图 G 1=（ V 1， E 1）和 G 2=( V 2， E 2)满足 V 2 V 1且 E 2 E 1，则称图 G 2是图 G 1的子图。

在无向图中，一个顶点的度等于与其相邻接的顶点个数。在有向图中，一个顶点的入度等于邻接到该顶点的顶点个数，其出度等于邻接于该顶点的个数。

在图 G =（ V ， E ）中，如果存在顶点序列（V0,V1,…,V k ）其中V0=P，V k =Q，且（V0，V1），（V1，V2），…，（Vk-1，V _k ）都在 E 中，则称顶点P到顶点Q有一条路径，并用（V0，V1，…，V k ）表示这条路径，路径的长度是路径的边数，这条路径的长度为 k 。若 G 是有向图，则路径也是有向的。

在有向图 G 中，若对于 V ( G )中任意两个不同的顶点V i 和V j ，都存在从V i 到V j 及从V j 到V i 的路径，则称 G 是强连通图。

有向图的极大强连通子图称为 G 的强连通分量。强连通图只有一个强连通分量，即是其自身。非强连通的有向图有多个强连分量。

2．图的存储结构

最常用的图的存储结构有邻接矩阵和邻接表。

1）邻接矩阵

邻接矩阵反映顶点间的邻接关系，设 G =（ V ， E ）是具有 n （ n ≥1）个顶点的图， G 的邻接矩阵 M 是一个 n 行 n 列的矩阵，并有若（ i ， j ）或＜ i ， j ＞∈ E ，则 M [ i ][ j ]=1；否则， M [ i ][ j ]=0。例如，图1-11（a）和（b）的邻接矩阵分别如下：

由邻接矩阵的定义可知，无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定对称。对于无向图，其邻接矩阵第 i 行元素的和即为顶点 i 的度。对于有向图，其邻接矩阵的第 i 行元素之和为顶点 i 的出度，而邻接矩阵的第 j 列元素之和为顶点 j 的入度。

若将图的每条边都赋上一个权，则称这种带权图为网（络）。如果图 G =（ V ， E ）是一个网，若（ i ， j ）或＜ i ， j ＞∈ E ，则邻接矩阵中的元素 M [ i ][ j ]为（ i ， j ）或＜ i ， j ＞上的权。若（ i ， j ）或＜ i ， j ＞∉ E ，则 M [ i ][ j ]为无穷大或为大于图中任何权值的实数。

2）邻接表

在图的邻接表中，为图的每个顶点建立一个链表，且第 i 个链表中的结点代表与顶点 i 相关联的一条边或由顶点 i 出发的一条弧。有 n 个顶点的图，需用 n 个链表表示，这 n 个链表的头指针通常由顺序线性表存储。例如，图1-11（a）和（b）的邻接表分别如图1-12（a）和（b）所示。

在无向图的邻接表中，对应某结点的链表的结点个数就是该顶点的度。在有向图的邻接表中，对应某结点的链表的结点个数就是该顶点的出度。

3．图的遍历

和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中每个顶点各做一次且仅做一次访问。它是许多图的算法的基础。深度优先遍历和广度优先遍历是最为重要的两种遍历图的方法。它们对无向图和有向图均适用。

1）深度优先遍历

在 G 中任选一顶点V为初始出发点（源点），则深度优先遍历可定义为首先访问出发点V，并将其标记为已访问过；然后依次从V出发搜索V的每个邻接点W。若W未曾访问过，则以W为新的出发点继续进行深度优先遍历，直至图中所有和源点V有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止。若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。

图的深度优先遍历类似于树的前序遍历。对于无向图，如果图是连通的，那么按深度优先遍历时，可遍历全部顶点，得到全部顶点的一个遍历序列。如果遍历序列没有包含所有顶点，那么该图是不连通的。

2）广度优先遍历

广度优先的遍历过程是：首先访问出发顶点V，然后访问与顶点V邻接的全部未被访问过的顶点W ₀ ,W ₁ ,…,W _{k -1} ；接着再依次访问与顶点W ₀ ,W ₁ ,…,W _{k -1} 邻接的全部未被访问过的顶点。依次类推，直至图的所有顶点都被访问到，或出发顶点V所在的连通分量的全部顶点都被访问到为止。

从广度优先搜索遍历过程可知，若顶点V在顶点W之前被访问，则对V相邻的顶点的访问就先于只与W相邻的那些顶点的访问。因此，需要一个队列来存放被访问过的顶点，以便按顶点的访问顺序依次访问这些顶点相邻接的其他还未被访问过的顶点。

1.3.2 最小生成树

如果连通图 G 的一个子图是一棵包含 G 的所有顶点的树，则该子图称为 G 的生成树。生成树是连通图的包含图中的所有顶点的极小连通子图。值得注意的是，图的生成树并不唯一。从不同的顶点出发进行遍历，可以得到不同的生成树。

含有 n 个顶点的连通图的生成树有 n 个顶点和 n –1条边。对一个带权的图（网），在一棵生成树中，各条边的权值之和称为这棵生成树的代价。其中代价最小的生成树称为最小代价生成树（简称最小生成树）。

MST性质：设 G =( V ， E )是一个连通网络， U 是顶点集 V 的一个真子集。若( u ， v )是 G 中所有的一个端点在 U （ u ∈ U ）里、另一个端点不在 U （即 v ∈ V – U ）里的边中，具有最小权值的一条边，则一定存在 G 的一棵最小生成树包括此边（ u ， v ）。

求连通的带权无向图的最小代价生成树的算法有普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。

1．普里姆算法

设已知 G =（ V ， E ）是一个带权连通无向图，顶点 V ={0,1,2,…, n – 1}。设 U 是构造生成树过程中已被考虑在生成树上的顶点的集合。初始时， U 只包含一个出发顶点。设 T 是构造生成树过程中已被考虑在生成树上的边的集合，初始时 T 为空。如果边（ i ， j ）具有最小代价，且 i ∈ U ， j ∈（ V – U ） ，那么最小代价生成树应包含边（ i ， j ）。把 j 加到 U 中，把（ i ， j ）加到 T 中。重复上述过程，直到 U 等于 V 为止。这时， T 即为要求的最小代价生成树的边的集合。

普里姆算法的特点是当前形成的集合 T 始终是一棵树。因为每次添加的边是使树中的权尽可能小，因此这是一种贪心的策略。普里姆算法的时间复杂度为 O （ n ² ），与图中边数无关，所以适合于稠密图。

2．克鲁斯卡尔算法

设 T 的初始状态只有 n 个顶点而无边的森林 T =( V ， )，按边长递增的顺序选择 E 中的 n – 1安全边( u ， v )并加入 T ，生成最小生成树。所谓安全边，是指两个端点分别是森林 T 里两棵树中的顶点的边。加入安全边，可将森林中的两棵树连接成一棵更大的树，因为每一次添加到 T 中的边均是当前权值最小的安全边，MST性质也能保证最终的 T 是一棵最小生成树。

克鲁斯卡尔算法的特点是当前形成的集合 T 除最后的结果外，始终是一个森林。克鲁斯卡尔算法的时间复杂度为 O （elog ₂ e），与图中顶点数无关，所以较适合于稀疏图。

1.3.3 最短路径

带权图的最短路径问题即求两个顶点间长度最短的路径。其中路径长度不是指路径上边数的总和，而是指路径上各边的权值总和。路径长度的具体含义取决于边上权值所代表的意义。

1．单源最短路径

已知有向带权图（简称有向网） G =( V ， E )，找出从某个源点 s ∈ V 到 V 中其余各顶点的最短路径，称为单源最短路径。

目前，求单源最短路径主要使用迪杰斯特拉（Dijkstra）提出的一种按路径长度递增顺序产生各顶点最短路径的算法。若按长度递增的次序生成从源点 s 到其他顶点的最短路径，则当前正在生成的最短路径上除终点以外，其余顶点的最短路径均已生成（将源点的最短路径看做是已生成的源点到其自身的长度为0的路径）。

迪杰斯特拉算法的基本思想是：设 S 为最短距离已确定的顶点集（看做红点集）， V – S 是最短距离尚未确定的顶点集（看做蓝点集）。

初始化：初始化时，只有源点 s 的最短距离是已知的（ SD ( s )=0），故红点集 S ={ s }，蓝点集为空。

重复以下工作，按路径长度递增次序产生各顶点最短路径：在当前蓝点集中选择一个最短距离最小的蓝点来扩充红点集，以保证算法按路径长度递增的次序产生各顶点的最短路径。当蓝点集中仅剩下最短距离为∞的蓝点，或者所有蓝点已扩充到红点集时， s 到所有顶点的最短路径就求出来了。

需要注意的是：

●　若从源点到蓝点的路径不存在，则可假设该蓝点的最短路径是一条长度为无穷大的虚拟路径；

●　从源点 s 到终点 v 的最短路径简称为 v 的最短路径； s 到 v 的最短路径长度简称为 v 的最短距离，并记为 SD ( v )。

根据按长度递增顺序产生最短路径的思想，当前最短距离最小的蓝点 k 的最短路径是：

源点红点1,红点2,…,红点 n ,蓝点 k

距离为：源点到红点 n 最短距离 + ＜红点 n ，蓝点 k ＞的边长。

为求解方便，可设置一个向量 D [0, n –1]，对于每个蓝点 v ∈ V – S ，用 D [ v ]记录从源点 s 到达 v 且除 v 外中间不经过任何蓝点（若有中间点，则必为红点）的“最短”路径长度（简称估计距离）。若 k 是蓝点集中估计距离最小的顶点，则 k 的估计距离就是最短距离，即若 D [ k ]=min{ D [ i ] i ∈ V – S }，则 D [ k ]= SD ( k )。

初始时，每个蓝点 v 的 D [ c ]值应为权 w ＜ s ， v ＞，且从 s 到 v 的路径上没有中间点，因为该路径仅含一条边＜ s ， v ＞。

将 k 扩充到红点后，剩余蓝点集的估计距离可能由于增加了新红点 k 而减小，此时必须调整相应蓝点的估计距离。对于任意的蓝点 j ，若 k 由蓝变红后使 D [ j ]变小，则必定是由于存在一条从 s 到 j 且包含新红点 k 的更短路径 P =＜ s ,…, k , j ＞。且 D [ j ]减小的新路径 P 只可能是由路径＜ s ,…, k ＞和边＜ k ， j ＞组成的。所以，当length( P )= D [ k ]+ w ＜ k ， j ＞小于 D [ j ]时，应该用 P 的长度来修改 D [ j ]的值。

2．每一对顶点之间的最短路径

对图中每对顶点 u 和 v ，找出 u 到 v 的最短路径问题。这一问题可用每个顶点作为源点调用一次单源最短路径问题的迪杰斯特拉算法予以解决。

但更常用的是弗洛伊德（Folyd）提出的求每一对顶点之间的最短路径的算法。设 G =( V ， E )是有 n 个顶点的有向图，顶点集合 V ={0,1,…, n – 1}。图用邻接矩阵 M 表示。Floyd算法的基本思想是递推地产生一个矩阵序列 C ₀ , C ₁ , C ₂ ,…, C _n ，其中 C ₀ 是已知的带权邻接矩阵 a ， C _k ( i ， j )（0≤ i ， j ＜ n ）表示从顶点 i 到顶点 j 的中间顶点序号不大于 k 的最短路径长度。如果 i 到 j 的路径没有中间顶点，则对于0≤ k ＜ n ，有 C _k ( i ， j ) = C ₀ ( i ， j ) = a [ i ][ j ]。递推地产生 C ₁ , C ₂ ,…, C _n 的过程就是逐步将可能是最短路径上的顶点作为路径上的中间顶点进行试探，直到为全部路径都找遍了所有可能成为最短路径上的中间顶点，所有的最短路径也就全部求出，算法就此结束。

设在第 k 次递推之前已求得 C _{k –1} ( i ， j )（0≤ i ， j ＜ n ），为求 C _k ( i ， j )需考虑以下两种情况。

●　如果从顶点i到顶点j的最短路径不经过顶点k，则由C _k (i，j)定义可知，从i到j中间的顶点序号不大于k的最短路径长度还是C _k –1(i，j)，即C _k (i，j)=C _{k –1} (i，j)。

●　如果从顶点i到顶点j的最短路径要经过顶点k，则这样的一条路径是由 i到k和由k到j的两条路径所组成的。由于C _{k –1} (i，k)和C _{k –1} (k，j)分别表示i到k和从k到j的中间顶点序号不大于k–1的最短路径长度，若C _{k –1} (i，k)+C _{k –1} (k，j) ＜C _{k –1} (i，j)，C _k – ₁ (i，k)+C _{k –1} (k，j)必定是i到j的中间顶点序号不大于k的最短路径的长度，则C _k (i，j)=C _{k –1} (i，k)+C _{k –1} (k，j)。

1.3.4 拓扑排序

对一个有向无环图 G 进行拓扑排序，是将 G 中所有顶点排成一个线性序列，使得图中任意一对顶点 u 和 v ，若＜ u ， v ＞∈ E ( G )，则 u 在线性序列中出现在 v 之前。这样的线性序列称为满足拓扑次序的序列，简称拓扑序列。

要注意的是：

●　若将图中顶点按拓扑次序排成一行，则图中所有的有向边均是从左指向右的；

●　若图中存在有向环，则不可能使顶点满足拓扑次序；

●　一个有向无环图可能有多个拓扑序列；

●　当有向图中存在有向环时，拓扑序列不存在。

一个大工程有许多项目组，有些项目的实行则存在先后关系，某些项目必须在其他一些项目完成之后才能开始实行。工程项目实行的先后关系可以用一个有向图来表示，工程的项目称为活动，有向图的顶点表示活动，有向边表示活动之间开始的先后关系。这种有向图称为用表活动网络，简称AOV网络，如图1-13所示。

对AOV网络的顶点进行拓扑排序，就是对全部活动排成一个拓扑序列，使得在AOV网络中存在一条弧（ i ， j ），则活动 i 排在活动 j 之前。例如对图1-35中的有向图的顶点进行拓扑排序，可以得到多个不同的拓扑序列，如02143567,02143657, 01243567等。

1.3.5 关键路径

在AOV网络中，如果边上的权表示完成该活动所需的时间，则称这样的AOV为AOE网络。例如图1-14表示一个具有10个活动的某个工程的AOE网络。图中有7个顶点，分别表示事件1～7，其中1表示工程开始状态，7表示工程结束状态，边上的权表示完成该活动所需的时间。

因AOE网络中的某些活动可以并行地进行，所以完成工程的最少时间是从开始顶点到结束顶点的最长路径长度，称从开始顶点到结束顶点的最长路径为关键路径（临界路径），关键路径上的活动为关键活动。

为了找出给定的AOE网络的关键活动，从而找出关键路径，先定义几个重要的量。

V _e ( j )、V _l ( j ) ：顶点 j 事件最早、最迟发生时间。

e( i )、 l ( i )：活动 i 最早、最迟开始时间。

从源点V ₁ 到某顶点V _j 的最长路径长度，称为事件V _j 的最早发生时间，记为 V _e ( j )。 V _e ( j )也是以V _j 为起点的出边＜V _j ,V _k ＞所表示的活动a _i 的最早开始时间e( i )。

在不推迟整个工程完成的前提下，一个事件V _j 允许的最迟发生时间，记为 V _l ( j )。显然， l ( i )= V _l ( j )-（a _i 所需时间），其中 j 为a _i 活动的终点。满足条件 l ( i )=e( i )的活动为关键活动。

求顶点 V _j 的 V _e ( j )和 V _l ( j )可按以下两步来做。

①由源点开始向汇点递推

其中， E ₁ 是网络中以 V _j 为终点的入边集合。

②由汇点开始向源点递推

其中， E ₂ 是网络中以V _j 为起点的出边集合。

要求一个AOE的关键路径，一般需要根据以上变量列出一张表格，逐个检查。例如求图1-14所示的AOE关键路径的过程如表1-1所示。

因此，图1-14的关键活动为a ₁ ,a ₂ ,a ₄ ,a ₈ 和a ₉ （即表1-1阴影所示活动），其对应的关键路径有两条，分别为（V ₁ ,V ₂ , V ₅ ,V ₇ ）和（V ₁ ,V ₄ ,V ₅ ,V ₇ ），长度都是10。 QtRZubhuT7Y9WYm9BzVrfVLxWWIiTL7yFMpA+7Y+97hISsG7nco95LNDn8feBlJt