第七章 图 ￡7.1 图的定义和术语 ￡7.2 图的存储结构 ￡7.3 图的遍历 ￡7.4 图的连通性问题 ￡7.5 有向无环图及其应用

Presentation on theme: "第七章 图 ￡7.1 图的定义和术语 ￡7.2 图的存储结构 ￡7.3 图的遍历 ￡7.4 图的连通性问题 ￡7.5 有向无环图及其应用"— Presentation transcript:

1 第七章 图 ￡7.1 图的定义和术语 ￡7.2 图的存储结构 ￡7.3 图的遍历 ￡7.4 图的连通性问题 ￡7.5 有向无环图及其应用
第七章 图 ￡7.1 图的定义和术语 ￡7.2 图的存储结构 ￡7.2.1 数组表示法 ￡7.2.2 邻接表 ￡7.2.3 十字链表 ￡7.2.4 邻接多重表 ￡7.3 图的遍历 ￡7.3.1 深度优先遍历 ￡7.3.2 广度优先遍历 ￡7.4 图的连通性问题 ￡7.4.1 无向图的连通分量和生成树 ￡7.4.2 最小生成树 ￡7.5 有向无环图及其应用 ￡7.5.1 有向无环图 ￡7.5.2 拓扑排序 ￡7.5.3 关键路径 ￡7.6 最短路径 ￡7.6.1 从某个源点到其余各顶点的最短路径 ￡7.6.2 每一对顶点之间的最短路径

2 图由结点及边(弧)组成,与树的主要区别在于图可以有回路
￡7.1 图的定义和术语 （1）形式化定义 Graph = (V, R) V = {x | x∈dataobject} //顶点的有穷非空集合 R = {VR} VR = {<v, w> | P(v, w)∩( v, w∈V)} //两个顶点之间的关系集合 （2）图形表示 G1 V V2 V3 V4 V3 V4 V5 V V2 G2 图由结点及边(弧)组成,与树的主要区别在于图可以有回路 (a) 有向图G1 (b) 无向图G2 图7.1 图的示例

3 A1 = {<v1, v2>, <v1, v3>, <v3, v4>, <v4, v1>}
(a) 有向图G1 G1＝(V1, { A1}) 其中：V1 = {v1, v2, v3, v4} A1 = {<v1, v2>, <v1, v3>, <v3, v4>, <v4, v1>} (b) 无向图G2 G2＝(V2, { E2}) 其中：V2 = {v1, v2, v3, v4, v5} E2 = {(v1, v2), (v1, v4), (v2, v3), (v2, v5), (v3, v4), (v3, v5)} （3）相关术语 顶点（Vertex）：图中的数据元素。 弧（Arc）：若<v, w>∈VR，则<v, w>表示从v到w的一条弧。 弧尾（Tail）或初始点（Initial node）：弧<v, w>的一个顶点v。 弧头（Head）或终端点（Terminal node）：弧<v, w>的一个顶点w。 有向图（Digraph）：由弧和顶点组成。 边（Edge）：若<v, w>∈VR必有<w, v>∈VR，即VR是对称的，则以 无序对(v, w)代替这两个有序对，表示v和w之间的一条边。 无向图（Undigraph）：由边和顶点组成。

4 若，用n表示图中顶点数目，用e表示边或弧的数目。且不考 虑顶点到其自身的边或弧，即若<vi, vj>∈VR，则vi≠vj。那么，
取值范围是0到n(n－1)。 无向完全图（Completed graph）：有 条边的无向图。 有向完全图：有n(n－1)条弧的有向图。 稀疏图（Sparse graph）：有很少条边或弧（如e < nlogn）的图。反之称为稠密 图（Dense graph）。 子图（Subgraph）：有两个图G=(V, {E})和G’=(V’, {E’})，如果V’ V且E’ 则称G’为G的子图。 E, V1 V4 V2 V3 (a) 图7.1中G1的子图

5 V1 V4 V2 V5 V3 (b) 图7.1中G2的子图 图7.2 子图示例 对于无向图G=(V, {E})，如果边(v, v’)∈E，则称顶点v和v’互为邻接点 （Adjacent）。边(v, v’)依附（Incident）于顶点v和v’，或者说(v, v’) 和顶 点v和v’相关联。 度：指和顶点v相关联的边的数目，记为TD(v)。 对于有向图G=(V, {A})，如果弧<v, v’>∈A，则称顶点v邻接到顶点v’， 顶点v’邻接自顶点v。弧<v, v’>和顶点v、v’相关联。 入度（InDegree）：以顶点v为头的弧的数目，记为ID(v)。 出度（OutDegree）：以顶点v为尾的弧的数目，记为OD(v)。 有向图中，顶点v的度为TD(v)＝ID(v)＋OD(v)。

6 一般地，如果顶点vi的度记为TD(vi)，那么一个有n个顶点，e条
边或弧的图，满足如下关系： 路径（Path）：在无向图G=(V, {E})中从顶点v到顶点v’的一个顶点序列 (v = vi,0, vi,1, …, vi,m = v’)，其中(vi,j-1, vi,j)∈E，1≤j≤m。若G是有向图，则路 径也是有向的，顶点序列满足<vi,j-1, vi,j>∈E，1≤j≤m。 路径的长度：路径上的边或弧的数目。 回路或环（Cycle）：第一个顶点和最后一个顶点相同的路径。 简单路径：序列中顶点不重复出现的路径。 简单回路或简单环：除了第一个顶点和最后一个顶点之外，其余顶点不 重复出现的回路。 连通：在无向图G中，如果从顶点v到顶点v’有路径，则称v和v’是连通的。 连通图（Connected Graph）：对于图中任意两个顶点vi, vj∈V，vi和vj都 是连通的图。 连通分量（Connected Component）：指无向图中的极大连通子图。

7 D E G H I K A B C D E F G H I K L M J A B C F J L M (a) 无向图G3
(b) G3的3个连通分量 图 无向图及其连通分量

8 强连通图：在有向图G中，如果对于每一对vi, vj∈V，vi≠vj，
从vi到vj都存在路径，则称G是强连通图。 强连通分量：有向图中的极大强连通子图。 生成树：一个连通图的生成树是一个极小连通子图。它含有图 中全部顶点，但只有足以构成一棵树的n－1条边。 A B C F J L M 图7.4 G3的最大连通分量的一棵生成树 由生成树的定义易知： ①一棵有n个顶点的生成树有且仅有n－1条边。 ②如果一个图有n个顶点和小于n－1条边，则是非连通图。 ③如果一个图有n个顶点和大于n－1条边，则一定有环。 ④有n－1条边的图不一定是生成树。

9 生成森林：一个有向图的生成森林由若干棵有向树组成，含有图 中全部的结点，但只有足以构成若干棵不相交的有向树的弧。
A B C F E D A D F B C E 图7.5 一个有向图及其生成森林 （4）图的抽象数据类型定义 ADT Graph { 数据对象V ：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系R： R = {VR} VR = {<v, w> | v, w∈V且P(v, w), <v, w> 表示从v到w的弧， 谓词P(v, w)定义了弧<v, w>的意义或信息 }

10 基本操作： CreateGraph (&G, V, VR); 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph (&G); 初始条件：图G存在。 操作结果：销毁图G。 LocateVex(G, u); 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置； 否则返回其他信息。 GetVex(G, v); 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex(&G, v, value); 操作结果：对v赋值value。 FirstAdjVex(G, v); 操作结果：返回v的第一个邻接顶点。若顶点在G中没有邻 接顶点，则返回“空”。

11 NextAdjVex(G, v, w); 初始条件：图G存在，v是G中某个顶点，w是v的邻接点。 操作结果：返回v的（相对于w的）下一个邻接顶点。若w 是v的最后一个邻接点，则返回“空”。 InsertVex(&G, v); 初始条件：图G存在，v和图中顶点有相同特征。 操作结果：在图G中增添新顶点v。 DeleteVex(&G, v); 初始条件：图G存在，v是G中某个顶点。 操作结果：删除G中顶点v及其相关的弧。 InsertArc(&G, v, w); 初始条件：图G存在，v和w是G中两个顶点。 操作结果：在图G中增添新弧<v, w>，若G是无向的，则还 增添对称弧<w, v>。 DeleteArc(&G, v, w); 操作结果：在图G中删除弧<v, w>，若G是无向的，则还删 除对称弧<w, v>。

12 BFSTraverse (G, visit());
操作结果：对图进行广度优先遍历。在遍历过程中对每个顶 点调用函数Visit一次且仅一次。一旦visit()失败， 则操作失败。 }ADT Graph DFSTraverse (G, visit()); 操作结果：对图进行深度优先遍历。在遍历过程中对每个顶

13 ￡7.2 图的存储结构 ￡7.2.1 数组表示法（邻接矩阵） （1）定义 数组表示法：用两个数组分别存储数据元素（顶点）的信
息和数据元素之间的关系（边或弧）的信息。 （2）C语言描述 #define INFINITY INT_MAX //最大值∞ #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef enum {DG, DN, UDG, UDN} GraphKind; //{有向图，有向网，无向图，无向网} typedef struct ArcCell { VRType adj; // VRType是顶点关系类型。对无权图，用1 //或0表示相邻否；对带权图，则为权值类型。 InfoType *info; //该弧相关信息的指针 } ArcCell, AdjMatrix[MAX_VERTEX_NUM][ MAX_VERTEX_NUM]; typedef struct { VertexType vexs[MAX_VERTEX_NUM]; //顶点向量 AdjMatrix arcs; //邻接矩阵 int vexnum, arcnum; //图的当前顶点数和弧数 GraphKind kind; //图的种类标志 } MGraph;

14 对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的 元素之和，即：
（3）邻接矩阵中顶点度的求法 对于无向图，顶点vi的度是邻接矩阵中第i行（或第i列）的 元素之和，即： 对于有向图，顶点vi的出度OD(vi)为第i行的元素之和，顶 点vi的入度ID(vi)为第j列的元素之和。 （4）网的邻接矩阵 网的邻接矩阵可定义为： wi,j 若<vi, vj>或(vi, vj) ∈VR A[i][j] = ∞ 反之 例如，下图列出了一个有向网和它的邻接矩阵。 4 5 3 8 7 9 1 6 V V2 V V3 V5 V4 (a) 网N (b) 邻接矩阵

15 （5）图的构造 算法7.1如下： Status CreateGraph (MGraph &G) { //采用数组（邻接矩阵）表示法，构造图G。 scanf (&G.kind); switch (G.kind) { case DG: return CreateDG; //构造有向图G case DN: return CreateDN; //构造有向网G case UDG: return CreateUDG; //构造无向图G case UDG: return CreateUDG; //构造无向网G default: return ERROR; } } // CreateGraph 算法7.1是在邻接矩阵存储结构MGraph上对图的构造操 作的实现框架，它根据图G的种类调用具体构造算法。

16 算法7.2构造一个具有n个顶点和e条边的无向网
G。其时间复杂度为O(n2+e*n)，其中对邻接矩 阵G.arcs的初始化耗费了O(n2)的时间。 算法7.2如下： Status CreateUDN (MGraph &G) { //采用数组（邻接矩阵）表示法，构造无向网G。 scanf (&G.vexnum, &G.arcnum, &IncInfo); //IncInfo为0则各弧不含其他信息 for (i = 0; i < G.vexnum; + + i) scanf (&G.vexs[i]); //构造顶点向量 for (i = 0; i < G.vexnum; + + i) //初始化邻接矩阵 for (j = 0; j < G.vexnum; + + j) G.arcs[i][j] = {INFINITY, NULL}; //{adj, info} for (k = 0; k < G.arcnum; + + k) { //构造邻接矩阵 scanf (&v1, &v2, &w); //输入一条边依附的顶点及权值 i = LocateVex (G, v1); //确定v1和v2在G中位置 j = LocateVex (G, v2); G.arcs[i][j].adj = w; //弧<v1, v2>的权值 if (IncInfo) Input (*G.arcs[i][j].info); //若弧含有相关信息，则输入 G.arcs[j][i] = G.arcs[i][j]; //置<v1, v2>的对称弧< v2, v1> } // for return OK; } // CreateUDN

17 ￡7.2.2 邻接表 （1）定义 邻接表（Adjacency List）：是图的一种链式存储结构。在
结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。 逆邻接表：即对每个顶点vi建立一个链接以vi为头的弧的表。 在逆邻接表中可以方便的确定顶点的入度或以顶点vi为头的弧。 （2）结点结构 表头结点通常以顺序结构的形式存储，以便随机访问任一顶点的链表。 表结点 adjvex nextarc info 头结点 data firstarc 表结点由3个域组成： adjvex：邻接点域，指示与顶点vi邻接的点在图中的位置。 nextarc：链域，指示下一条边或弧的结点。 info：数据域，存储和边或弧相关的信息，如权值等。 头结点由2个域组成： data：数据域，存储顶点vi的名或其他有关信息。 firstarc：链域，指向链表中第一个结点。

18 （3）C语言描述 #define MAX_VERTEX_NUM 20 typedef struct ArcNode { int adjvex; //该弧所指向的顶点的位置 struct ArcNode *nextarc; //指向下一条弧的指针 InfoType *info; //该弧相关信息的指针 } ArcNode; typedef struct VNode { VertexType data; //顶点信息 struct ArcNode * firstarc; //指向第一条依附该顶点的弧的指针 } VNode, AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum, arcnum; //图的当前顶点数和弧数 kind kind; //图的种类标志 } ALGraph;

19 （4）图形表示 G2 G1 (a) 有向图 和无向图 G1 G2 V1 V2 V3 V4 1 2 3 2 1 V1 V2 V3 V4 1 2
1 2 3 V1 V2 V3 V4 1 2 3 (c) G1的逆邻接表 (b) G1的邻接表

20 对于无向图，顶点vi的度恰为第i个链表中的结点数。 对于有向图，顶点vi的出度OD(vi)为第i个链表中的结点个数；求顶点vi的
1 2 3 V5 4 (d) G2的邻接表 图 邻接表和逆邻接表 （5）邻接表中顶点度的求法 对于无向图，顶点vi的度恰为第i个链表中的结点数。 对于有向图，顶点vi的出度OD(vi)为第i个链表中的结点个数；求顶点vi的 入度ID(vi)必须遍历整个邻接表，查找所有链表中其邻接点域的值为i的结点， 它们的总和即为顶点vi的入度。

21 ￡7.2.3 十字链表（有向图） 弧结点 （1）定义 十字链表（Orthogonal List）：是有向图的另一种链式存储结构。可
以看成是将有向图的邻接表和逆邻接表结合起来得到的一种链表。也即弧 头相同的弧在同以一链表上，弧尾相同的弧也在同一链表上 （2）结点结构 tailvex headvex hlink tlink info data firstin firstout 弧结点 头结点（顶点结点） 弧结点由5个域组成： tailvex：尾域，指示弧尾顶点在图中的位置。 headvex：头域，指示弧头顶点在图中的位置。 hlink：链域，指向弧头相同的下一条弧。 tlink：链域，指向弧尾相同的下一条弧。 info：数据域，指向该弧的相关信息。 头结点由3个域组成： data：数据域，存储和顶点相关的信息，如顶点名称等。 firstin：链域，指向以该顶点为弧头的第一个弧结点。 firstout：链域，指向以该顶点为弧尾的第一个弧结点。

22 （3）C语言描述 #define MAX_VERTEX_NUM 20 typedef struct ArcBox { int tailvex, headvex; //该弧的尾和头顶点的位置 struct ArcBox * hlink, * tlink; //分别为弧头相同和弧尾相同的弧的链域 InfoType *info; //该弧相关信息的指针 } ArcBox; typedef struct VexNode { VertexType data; ArcBox * firstin, * firstout; //分别指向该顶点第一条入弧和出弧 } VexNode; typedef struct { VexNode xlist[MAX_VERTEX_NUM]; //表头向量 int vexnum, arcnum; //有向图的当前顶点数和弧数 } OLGraph;

23 （4）图形表示 V V2 (a) V V4 V1 (b) 0 1 V2 1 V3 2 V4 3 0 2 2 0 3 0 2 3 3 1 3 2 图7.7 有向图的十字链表

24 （5）图的构造 算法7.3如下： Status CreateDG (OLGraph &G) { //采用十字链表存储表示，构造有向图G(G.kind = DG)。 scanf (&G.vexnum, &G.arcnum, &IncInfo); //IncInfo为0则各弧不含其他信息 for (i = 0; i < G.vexnum; + + i) { //构造表头向量 scanf (&G.xlist[i].data); //输入顶点值 G.xlist[i].firstin = NULL; //初始化指针 G.xlist[i].firstout = NULL; } for (k = 0; k < G.arcnum; + + k) { //输入各弧并构造十字链表 scanf (&v1, &v2); //输入一条弧的始点和终点 i = LocateVex (G, v1); //确定v1和v2在G中位置 j = LocateVex (G, v2); p = (ArcBox *) malloc (sizeof (ArcBox)); //假定有足够空间 * p = {i, j, G.xlist[j].firstin, G.xlist[j].firstout, NULL}; //对弧结点赋值 {tailvex, headvex, hlink, tlink, info} G.xlist[j].firstin = G.xlist[j].firstout = p; //完成在入弧和出弧链头的插入 if (IncInfo) Input (*p－>info); //若弧含有相关信息，则输入 } // for } // CreateDG

25 ￡7.2.4 邻接多重表（无向图） （1）定义 邻接多重表（Adjacency Multilist）：是无向图的另一种链式
存储结构。邻接多重表的结构和十字链表类似。在邻接多重表中， 所有依附于同一顶点的边串联在同一链表中，由于每条边依附两个 顶点，则每个边结点同时链接在两个链表中。 （2）结点结构 mark ivex ilink jvex jlink info 顶点结点 边结点 data firstedge 在邻接多重表中,每一条边用一个结点表示,每一个顶点也用一个结点表示。 边结点由6个域组成： mark：标志域，用以标记该条边是否被搜索过。 ivex和jvex：为该边依附的两个顶点在图中的位置。 ilink：链域，指向下一条依附于顶点ivex的边。 jlink：链域，指向下一条依附于顶点jvex的边。 info：数据域，指向和边相关的各种信息的指针域。 顶点结点有2个域组成： data：数据域，存储和该顶点相关的信息。 firstedge：链域，指示第一条依附于该顶点的边。

26 （3）C语言描述 #define MAX_VERTEX_NUM 20 typedef emnu {unvisited, visited} VisitIf; typedef struct EBox { VisitIf mark; //访问标记 int ivex, jvex; //该边依附的两个顶点的位置 struct EBox * ilink, * jlink; //分别指向依附这两个顶点的下一条边 InfoType *info; //该边信息指针 } EBox; typedef struct VexBox { VertexType data; EBox * firstedge; //分别指向该顶点第一条入弧和出弧 } VexBox; typedef struct { VexBox adjmulist[MAX_VERTEX_NUM]; int vexnum, edgenum; //无向图的当前顶点数和边数 } AMLGraph;

27 （4）图形表示 G2 V V2 V V5 V3 4 V1 V2 1 V3 2 V4 3 V5 图7.8 无向图G2的邻接多重表

28 ￡7.3 图的遍历 ￡7.3.1 深度优先遍历 图的遍历（Traversing Graph）：从图中某一顶点出发，
访遍图中其余顶点，且使每一个顶点仅被访问一次的过程。 ￡7.3.1 深度优先遍历 （1）定义 深度优先遍历（Depth_First Search）类似于树的先根遍历， 是树的先根遍历的推广。 主要思想：假设初始状态是图中所有顶点未曾被访问，则深度优先搜索可从图中某个顶点v出发，访问此顶点，然后依次从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

29 以图7.9(a)中无向图G4为例，深度优先搜索遍历图。
（2）深度优先搜索遍历图的过程演示 以图7.9(a)中无向图G4为例，深度优先搜索遍历图。 V1 V2 V3 V4 V5 V6 V7 V8 1 2 5 7 3 4 8 G4 V1 V2 V3 V4 V5 V6 V7 V8 (a) 无向图 (b) 深度优先搜索的过程 图 遍历图的过程 说明：假设从v1出发进行搜索，在访问了顶点v1之后，选择邻接点v2。因为v2 未曾访问，则从v2成分进行搜索。依次类推，接着从v4，v8，v5出发进行搜索。 在访问了v5之后，由于v5的邻接点都已被访问，则搜索回到v8。同理，搜索继续 回到v4，v2直至v1，此时由于v1的另一个邻接点未被访问，则搜索又从v1到v3，再 继续进行下去。得到的顶点访问序列为：

30 （3）遍历算法 // 算法7.4和7.5使用的全局变量 Boolean visited[MAX]; //访问标志数组 Status (* VisitFunc) (int v); //函数变量 算法7.4如下： void DFSTraverse (Graph G, Status (* Visit) (int v)) { //对图G作深度优先遍历 VisitFunc = Visit; //使用全局变量VisitFunc,使DFS不必设函数指针参数 for (v = 0; v < G.vexnum; ++ v) visited[v] = FALSE; //访问标志数组初始化 if (!visited[v]) DFS (G, v); //对尚未访问的顶点调用DFS } 算法7.5如下： void DFS (Graph G, int v) { //从第v个顶点出发递归地深度优先遍历图G。 visited[v] = TRUE; VisitFunc (v); //访问第v个顶点 for (w = FirstAdjVex(G, v); w >= 0; w = NextAdjVex (G, v, w)) if (!visited[w]) DFS(G, w); //对v尚未访问的邻接顶点w递归调用DFS }

31 ￡7.3.2 广度优先遍历 （1）定义 广度优先遍历（Breadth_First Search）类似于树的按层次遍历的过程。
主要思想：假设从图中某顶点v出发，在访问了v之后依次访问v的各个未 曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并 使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至 图中所有已被访问的顶点的邻接点都被访问到。若此时图中尚有顶点未被访 问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中 所有顶点都被访问到为止。 （2）广度优先搜索遍历图的过程演示 以图7.9(a)中无向图为例，广度优先搜索遍历图。

32 V1 V2 V3 V4 V5 V6 V7 V8 1 2 5 7 3 4 8 6 图7.10 广度优先搜索的过程 说明：假设从v1出发进行搜索。首先访问v1和v1的邻接点v2和v3，然后依 次访问v2的邻接点v4和v5及v3的邻接点v6和v7，最后访问v4的邻接点v8。由于 这些顶点的邻接点均已被访问，并且图中所有顶点都被访问，由此完成了图的 遍历。 得到的顶点访问序列为：

33 （3）遍历算法 算法7.6如下： void BFSTraverse (Graph G, Status (* Visit) (int v)) { //按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。 for (v = 0; v < G.vexnum; ++ v) visited[v] = FALSE; InitQueue (Q); //置空的辅助队列Q if (!visited[v]) { //v尚未访问 visited[v] = TRUE; Visit (v); EnQueue (Q, v); //v入队列 while (!QueueEmpty(Q)) { DeQueue (Q, u); //队头元素出队并置为u for (w = FirstAdjVex (G, u); w >= 0; w = NextAdjVex (G, u, w)) if (!Visited[w]) { //w为u的尚未访问的邻接顶点 visited[w] = TRUE; Visit (w); EnQueue (Q, w); } // if } // while } // BFSTraverse

34 广度优先生成树：在连通图中，由广度优先搜索得到的生成树。
￡7.4 图的连通性问题 ￡7.4.1 无向图的连通分量和生成树 （1）连通图 在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发， 进行深度优先搜索或广度优先搜索，便可访问到图中所有结点。 深度优先生成树：在连通图中，由深度优先搜索得到的生成树。 广度优先生成树：在连通图中，由广度优先搜索得到的生成树。 （2）非连通图 在对无向图进行遍历时，对于非连通图，需从多个顶点出发进行 搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访 问序列恰为其各个连通分量中的顶点集。 生成森林：在非连通图中，每个连通分量中的顶点集和遍历时走 过的边一起构成若干棵生成树，这些连通分量的生成树组成非连通图 的生成森林。 深度优先生成森林：在非连通图中，由深度优先搜索得到的生成 森林。 广度优先生成森林：在非连通图中，由广度优先搜索得到的生成 森林。

35 （3）图形表示 V1 V2 V3 V4 V5 V6 V7 V8 A 1 L 2 F 6 C 7 M 3 J 4 B 5 A B C D E
G4 V1 V2 V3 V4 V5 V6 V7 V8 V2 V3 V4 V5 V6 V7 V8 V1 V1 V2 V3 V4 V5 V6 V7 V8 (a) 图7.9(a) G4的深度优先生成树 (b) 图7.9(a) G4的广度优先生成树 A 1 L 2 F 6 C 7 M 3 J 4 B 5 G3 A B C D E F G H I K L M J G 10 K 11 I 13 H 12 D 8 E 9 (c) 图7.3(a) G3的深度优先生成森林 图 生成树和生成森林

36 （4）非连通图的深度优先森林的生成算法 算法7.7如下： void DFSForest (Graph G, CSTree &T) { //建立无向图G的深度优先生成森林的（最左）孩子（右）兄弟链表T。 T = NULL; for (v = 0; v < G.vexnum; ++ v) visited[v] = FALSE; if (!visited[v]) { //第v顶点为新的生成树的根结点 p = (CSTree) malloc (sizeof (CSNode)); //分配根结点 * p = {GetVex(G, v), NULL, NULL}; //给该结点赋值 if (!T) T = p; //是第一棵生成树的根（T的根） else q－>nextsibling = p; //是其他生成树的根(前一棵的根的“兄弟”) q = p; //q指示当前生成树的根 DESTree (G, v, p); //建立以p为根的生成树 } } // DFSForest

37 算法7.8如下： void DFSTree (Graph G, int v, CSTree &T) { //从第v个顶点出发深度优先遍历图G，建立以T为根的生成树 visited[v] = TRUE; first = TRUE; for (w = FirstAdjVex (G, v); w >= 0; w = NextAdjVex (G, v, w) ) if (!visited[w]) { p = (CSTree) malloc (sizeof (CSNode)); //分配孩子结点 * p = {GetVex(G, w), NULL, NULL}; if (first) { //w是v的第一个未被访问的邻接顶点 T－>lchild = p; first = FALSE; //是根的左孩子结点 } // if else { //w是v的其他未被访问的邻接顶点 q－>nextsibling = p; //是上以邻接顶点的右兄弟结点 } // else q = p; DESTree (G, w, q); //从第w个顶点出发深度优先遍历图G，建立子生成树q } // DFSTree

38 ￡7.4.2 最小生成树 最小生成树的MST性质：假设N = (G, {E})是一个连通网，U是顶点
集V的一个非空子集。若(u, v)是一条具有最小权值（代价）的边，其中 u∈U, v∈V－U， 则必存在一棵包含边(u, v)的最小生成树。 （1）普里姆（Prim）算法 ①算法思想 假设N = (V, {E})是连通网，TE是N上最小生成树中边的集合。 算法从U={u0}(u0∈V)，TE = { }开始，重复执行下述操作：在所 有u∈U，v∈V-U的边(u, v)∈E中找一条代价最小的边(u0, v0)并入集合 TE，同时v0并入U，直至U=V为止。此时TE中必有n－1条边，则 T = (V, {TE})为N的最小生成树。 ②算法实现 为实现算法需附设一个辅助数组closedge，以记录从U到V-U具有 最小代价的边。对每个顶点vi∈V-U，在辅助数组中存在一个相应分量 closedge[i－1]，它包括两个域，其中lowcost存储该边上的权。显然， closedge [i－1].lowcost = Min {cost (u, vi) | u∈U} vex域存储该边依附的在U中的顶点。

39 假设以二维数组表示网的邻接矩阵，且令两个顶点之间不存在的边的权值为机内允许的最大值（INT_MAX），则Prim算法如下所示。
算法7.9如下： void MiniSpanTree_PRIM (MGraph G, VertexType u) { //用Prim算法从第u个顶点出发构造网G的最小生成树T，输出T的各条边。 //记录从顶点集U到V－U的代价最小的边的辅助数组定义： // struct { // VertexType adjvex; // VRType lowcost; // } closedge[MAX_VERTEX_NUM]; k = LocateVex (G, u); for (j = 0; j < G.vexnum; ++ j) //辅助数组初始化 if (j != k) closedge[j] = {u, G.arcs[k][j].adj}; //{adjvex, lowcost} closedge[k].lowcost = 0; //初始，U = {u}

40 for (i = 0; i < G.vexnum; ++ i) { //选择其余G.vexnum－1个顶点
k = minimum (closedge); //求出T的下一个结点：第k顶点 //此时closedge[k].lowcost = // MIN{ closedge[vi].lowcost | closedge[vi].lowcost > 0, vi∈V-U} printf (closedge[k].adjvex, G.vexs[k]); //输出生成树的边 closedge[k].lowcost = 0; //第k顶点并入U集 for (j = 0; j < G.vexnum; ++ j) if (G.arcs[k][j].adj < closedge[j].lowcost) //新顶点并入U后重新选择最小边 closedge[j] = {G.vexs[k], G.arcs[k][j].adj }; } // for } // MiniSpanTree_PRIM 时间复杂度：O(n2)。其中n为网中的顶点数。可见， 其时间复杂度与网中的边数无关，因此适用于求边 稠密的网的最小生成树。

41 例如，图7.12所示为按Prim算法构造网的一棵最小生成树的过程，在构 造过程中各分量的变化如图7.13所示。
③例子 例如，图7.12所示为按Prim算法构造网的一棵最小生成树的过程，在构 造过程中各分量的变化如图7.13所示。 V1 V2 V4 V3 V6 V5 6 5 3 1 4 2 V1 V2 V4 V3 V6 V5 V1 V2 V4 V3 V6 V5 1 4 (a) (b) (c) V1 V2 V4 V3 V6 V5 1 4 2 1 V1 V2 V4 V3 V6 V5 5 4 2 V1 V2 V4 V3 V6 V5 3 1 4 2 5 (d) (e) (f) 图 Prim算法构造最小生成树的过程

42 图7.13 图7.12构造最小生成树过程中辅助数组中各分量的值
closedge U V－U k i adjvex v v v {v1} {v2,v3,v4, 2 lowcost v5,v6} adjvex v v v v3 {v1, v3} {v2, v4, lowcost v5,v6} adjvex v v {v1, v3, {v2, v5 } lowcost v6, v4} adjvex v v v {v1, v3, {v2, v4, lowcost v6} v5 } adjvex v {v1, v3, { v5} lowcost v6, v4, v2} adjvex {v1, v3, v6, { } lowcost v4, v2, v5} 图 图7.12构造最小生成树过程中辅助数组中各分量的值 说明：初始状态时，由于U={v1}，则到V－U中各顶点的最小边，即为从依附 于顶点1的各条边中，找到一条代价最小的边(u0, v0) = (1, 3)为生成树上的第一条边， 同时将v0(=v3)并入集合U。然后修改辅助数组中的值。首先将closedge[2].lowcost改 为’0’以示顶点v3已并入U。然后，由于边(v3, v2)上的权值小于closedge[1].lowcost， 则需修改closedge[1]为边(v3, v2)及其权值。同理修改closedge[4]和closedge[5]。依次 类推，直到U = V。

43 （2）克鲁斯卡尔（Kruskal）算法 ①算法思想 假设连通网N = (V, {E})，则令最小生成树的初始状态为只有n个顶点而无
边的非连通图T = (V, { })，图中每个顶点自成一个连通分量。在E中选择代价 最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。依次类推，直至T中所有顶点 都在同一连通分量上为止。 ②时间复杂度 Kruskal算法的时间复杂度为：O(eloge)(e为网中边的数目)，因此其相对 于Prim算法而言，适合于求边稀疏的网的最小生成树。 ③例子 例如，图7.14所示为依照Kruskal算法构造一棵最小生成树的过程。 V1 V2 V4 V3 V6 V5 6 5 3 1 4 2 V1 V2 V4 V3 V6 V5 1 V1 V2 V4 V3 V6 V5 1 2 (a) (b) (c)

44 图7.14 Kruskal算法构造最小生成树的过程
V1 V2 V4 V3 V6 V5 1 2 3 V1 V2 V4 V3 V6 V5 1 2 3 4 V1 V2 V4 V3 V6 V5 3 1 4 2 5 (d) (e) (f) 图 Kruskal算法构造最小生成树的过程 说明：代价分别为1，2，3，4的4条边由于满足上述条件，则先后被加入到T 中，代价为5的两条边(v1, v4)和(v3, v4)被舍去。因为它们依附的两顶点在同一连 通分量上，它们若加入T中，则会使T中产生回路，而下一条代价(=5)最小的边 (v2, v3)联结两个连通分量，则可加入T。由此构造一棵最小生成树。

45 ￡7.5 有向无环图及其应用 ￡7.5.1 有向无环图 有向无环图（directed acycline graph）：无环的有向图，简称DAG 图。DAG图是一类较有向树更一般的特殊有向图。 例如，图7.15示例了有向树、DAG图和有向图的例子。 图7.15 有向树、DAG图和有向图一例

46 （2）表达式子式共享 例如，下述表达式((a +b ) * (b * (c + d)) + (c + d) * e) * ((c + d) * e)，用 二叉树表示如图7.16所示，用有向无环图表示如图7.17所示。 * + e a b c d 图7.16 用二叉树描述表达式

47 * + e a b c d 图 描述表达式的有向无环图

48 ￡7.5.2 拓扑排序 （1）定义 拓扑排序（Topological Sort）：简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。 偏序关系：若集合X上的关系R是自反的、反对称的和传递的，则称R是集合X上的偏序关系。 全序关系：R是集合X上的偏序，若对每个x, y∈X必有xRy或yRx， 则称R是集合X上的全序关系。 （2）AOV-网 AOV-网：用顶点表示活动，用弧表示活动间的优先关系的有向图 称为顶点表示活动的网（Activity On Vertex Network），简称AOV-网。 在网中，若从顶点i到顶点j有一条有向路径，则i是j的前驱； j是i的后继。若<i, j>是网中的一条弧，则i是j的直接前驱； j是i的直接后继。

49 例如，一个软件专业的学生必须学习一系列基本课程(如图7.18所示)， 其中有些课程是基础课，它独力于其他课程，如《高等数学》；而另一些
课程必须在学完作为它的基础的先修课程才能开始。如，在《程序设计基 础》和《离散数学》学完之前就不能开始学习《数据结构》。这些先决条 件定义了课程之间的领先（优先）关系。这个关系可以用有向图7.19清楚 的表示。 课程编号 课程名称 先决条件 C 程序设计基础 无 C 离散数学 C1 C 数据结构 C1，C2 C 汇编语言 C1 C 语言的设计和分析 C3，C4 C 计算机原理 C11 C 编译原理 C3，C5 C 操作系统 C3，C6 C 高等数学 无 C 线性代数 C9 C 数值分析 C9，C10，C1 C 普通物理 C9 图7.18 软件专业的学生必须学习的课程

50 图7.19中，顶点表示课程，有向边（弧）表示先决条件。若课程i是 课程j的先决条件，则图中有弧<i, j>。
C4 C5 C1 C2 C3 C7 C12 C8 C6 C9 C10 C11 图 表示课程之间优先关系的有向图 图7.19中，顶点表示课程，有向边（弧）表示先决条件。若课程i是 课程j的先决条件，则图中有弧<i, j>。 如下，为图7.19中的有向图的拓扑有序序列的其中两个序列： 1．(C1, C2, C3, C4, C5, C7, C9, C10, C11, C6, C12, C8) 2．(C9, C10, C11, C6, C1, C12, C4, C2, C3, C5, C7, C8)

51 （3）拓扑排序 ①算法思想： 1．在有向图中选一个没有前驱的顶点且输出之。 2．从图中删除该顶点和所有以它为尾的弧。 3．重复上述两步，直至全部顶点均已输出，或者当前图中步存在 无前驱的顶点为止。 ②算法实现： 针对上述操作，采用邻接表作有向图的存储结构，且在头结点中 增加一个存放顶点入度的数组（indegree）。入度为0的顶点即为没有 前驱的顶点，删除顶点及以它为弧的操作，则可换以弧头顶点的入度 减1来实现。 算法7.10如下： Status TopologicalSort (ALGraph G) { //有向图G采用邻接表存储结构。 //若G无回路，则输出G的顶点的一个拓扑序列，并返回OK，否则ERROR。 FindInDegree (G, indegree); //对各顶点求入度indegree[0..vernum－1] InitStack (S); for (i = 0; i < G.vexnum; ++i) //建0入度顶点栈S if (!indegree[i]) Push (S, i); //入度为0者进栈

52 count = 0; while (!StackEmpty (S)) { Pop (S, i); printf (i, G.vertices[i].data); //输出i号顶点并计数 ++ count; for (p = G.vertices[i].firstarc; p; p = p－>nextarc) { k = p－>adjvex; //对i号顶点的每个邻接点的入度减1 if (!(――indegree[k])) Push (S, k); //若入度减为0，则入栈 } // for } // while if (count < G.vexnum) return ERROR; //该有向图有回路 } // TopologicalSort 时间复杂度：O(n + e)。

53 (a) AOV-网； (b) 输出v6之后； (c) 输出v1之后； (d) 输出v4之后； (e) 输出v3之后； (f) 输出v2之后；
③例子 以图7.20(a)中的有向图为例。 V1 V2 V4 V3 V6 V5 V1 V2 V4 V3 V5 V2 V4 V3 V5 V2 V3 V5 V2 V5 V5 图 AOV-网及其拓扑有序序列产生的过程 (a) AOV-网； (b) 输出v6之后； (c) 输出v1之后； (d) 输出v4之后； (e) 输出v3之后； (f) 输出v2之后； 。 说明：图中v1和v6没有前驱，则可任选一个。假设先输出v6，在输出v6及弧 < v6, v4>,< v6, v5>之后，只有顶点v1没有前驱，则输出v1且删去v1及弧< v1, v2>, < v1, v3>和< v1, v4>，之后v3和v4都没有前驱。依次类推，可从中任选一个继续进 行。最后得到该有向图的拓扑有序序列为：

54 ￡7.5.3 关键路径 （1）定义 关键路径（Critical Path）：在AOE-网中有些活动可以并行的进行，
所以完成工程的最短时间是从开始点到完成点的最长路径的长度（路径 长度是指路径上各活动持续时间之和，而不是路径上弧的数目）。这个 路径长度最长的路径叫关键路径。 关键活动：l(i) = e(i)的活动。即活动的最早开始时间＝最迟开始时间。 显然，关键路径上的所有活动都是关键活动。 （2）AOE-网 AOE-网（Activity On Edge）：即边表示活动的网。AOE-网是一个 带权的有向无环图。其中，顶点表示事件（Event），弧表示活动，权 表示活动持续的时间。

55 例如，通常，AOE-网可用来估算工程的完成时间。图7.21是一个假想的
有11项活动的AOE-网。其中有9个事件v1, v2, v3, … , v9，每个事件表示在它 之前的活动已经完成，在它之后的活动可以开始。与每个活动相联系的数是 执行该活动所需的时间。 V2 V1 V3 V5 V7 V4 V8 V9 V6 a1= a4= a7= a10=2 a2= a5=1 a8= a11=4 a3= a9=4 a6=2 图 一个AOE-网 其中，v1为源点（入度为零的点）；v9为汇点（出度为零的点）。

56 （3）事件的最早发生时间ve(j)和最迟发生时间vl(j)
ve(j) = Max{ve(i) + dut(<i, j>)} <i, j>∈T, j = 1, 2, … , n－1 其中，T是所有以第j个顶点为头的弧的集合。dut(<i, j>)是由<j , k>弧 表示的活动的持续时间。 ②从vl(n－1) = ve(n－1)起向后递推 vl(i) = Min{vl(j)－dut(<i, j>)} <i, j>∈S, i = n－2, … , 0 其中，S是所有以第i个顶点为尾的弧的集合。 （4）活动的最早发生时间和最迟发生时间 最早开始时间：假设开始点是v1，从v1到vi的最长路径长度叫做事件vi 的最早发生时间。这个时间决定了所有以vi为尾的弧所表示的活动的最早 开始时间。记为e(i)，表示活动ai的最早开始时间。 最迟开始时间：在不推迟整个工程完成的前提下，活动ai最迟必须开始 进行的时间。记为l(i)，表示活动ai的最迟开始时间。 如果活动ai由弧<j , k>表示，其持续时间记为dut(<j, k>)，则 e(i) = ve(j) l(i) = vl(k) －dut(<j, k>)

57 （5）关键路径算法 ①算法思想： 1．输入e条弧<j, k>，建立AOE-网的存储结构； 2．从源点v0出发，令ve[0] = 0，按拓扑有序求其余各顶点的最早发 生时间ve[i](1≤i≤n－1)。如果得到的拓扑有序序列中顶点个数小于网中 顶点数n，则说明网中存在环，不能求关键路径，算法终止；否则执行步 骤3。 3．从汇点vn出发令vl[n－1] = ve[n－1]，按逆拓扑有序求其余各顶 点的最迟发生时间veli]( 2≤i≤n－2)； 4．根据各顶点的ve和vl值，求每条弧s的最早开始时间e(s)和最迟开 始时间l(s)。若某条弧满足条件e(s) = l(s)，则为关键活动。 ②算法实现 如①所述，计算各顶点的ve值是在拓扑排序的过程中进行的，需对 拓扑排序的算法作如下修改： 1．在拓扑排序之前设初值，令ve[i]＝0(0≤i≤n－1)； 2．在算法中增加一个计算vj的之间后继vk的最早发生时间的操作： 若ve(j) + dut(<j, k>) > ve[k]，则ve[k]＝ve(j) + dut(<j, k>)； 3．为了能按逆拓扑有序序列的顺序计算各顶点的vl值，需记下在拓 扑排序的过程中求得的拓扑有序序列，这需要在拓扑排序算法中，增设 一个栈以记录拓扑有序序列，则在计算求得各顶点的ve值之后，从栈顶至 栈底便为逆拓扑有序序列。

58 算法7.11如下 (由算法7.10改写而成) ： Status TopologicalOrder (ALGraph G, Stack &T) { //有向网G采用邻接表存储结构，求各顶点事件最早发生时间ve // （全局变量）。 T为拓扑序列顶点栈，S为零入度顶点栈。 //若G无回路，则用栈T返回G的一个拓扑序列，且函数值为OK， //否则ERROR。 FindInDegree (G, indegree); //对各顶点求入度indegree[0..vernum-1] 建0入度顶点栈S; InitStack (T); //初始化 count = 0; ve[0..G.vexnum－1] = 0; while (!StackEmpty (S)) { Pop (S, j); Push (T, j); //j号顶点入T栈并计数 + + count; for (p = G.vertices[i].firstarc; p; p = p－>nextarc) { k = p－>adjvex; //对j号顶点的每个邻接点的入度减1 if ((――indegree[k]) = = 0) Push (S, k); //若入度减为0，则入栈

59 if (ve[j] + * (p－>info) > ve[k])
ve[k] = ve[j] + *( p－>info); } // for * (p－>info) = dut (<j, k>) } // while if (count < G.vexnum) return ERROR; //该有向网有回路 } // TopologicalOrder 算法7.12如下(求关键路径)： Status CriticalPath (ALGraph G) { //G为有向网，输出G的各项关键活动。 if (!TopologicalOrder (G, T)) return ERROR; vl[0..G.vexnum－1] = ve[0..G.vexnum－1]; //初始化顶点事件的最迟发生时间

60 while (!StackEmpty (T)) //按拓扑逆序求各顶点的vl值
for (Pop (T, j), p = G.vertices[i].firstarc; p; p = p－>nextarc) { k = p－>adjvex; dut = *( p－>info); //dut<j, k> if (vl[k]－dut < vl[j]) vl[j] = vl[k]－dut; } // for for (j = 0; j < G.vexnum; ++ j) //求ee，el和关键活动 for (p = G.vertices[j].firstarc; p; p = p－>nextarc) { dut = *( p－>info); ee = ve[j]; el = vl[k]－dut; tag = (ee = = el) ? ‘*’ : ‘’; printf (j, k, dut, ee, el, tag); //输出关键活动 } } // CriticalPath 时间复杂度：O(n + e)。

61 例如，对图7.22(a)所示的计算结果如图7.23所示，可见a2、a5和a7为关键
③例子 例如，对图7.22(a)所示的计算结果如图7.23所示，可见a2、a5和a7为关键 活动，组成一条从源点到汇点的关键路径，如图7.22(b)所示。 a7=2 a4=3 V V5 a1= a3= a8=1 V V V6 a5=4 a2= a6=3 V3 a7 a5 V V V6 a2 V3 (b) 关键路径 (a) AOE-网 图 AOE-网及其关键路径

62 a7=2 a4=3 V V5 a1= a3= a8=1 V V V6 a5=4 a2= a6=3 V3 a 顶点 ve vl 活动 e l l－e v a v a v a v a v a v a a 图 图7.22(a)所示AOE-网中顶点的发生时间和活动开始时间

63 ￡7.6 最短路径 ￡7.6.1 从某个源点到其余各顶点的最短路径 Dijkstra（迪杰斯特拉）算法： （1）算法思想：
按路径长度递增的次序产生最短路径的算法。 1．假设用带权的邻接矩阵arcs来表示带权有向图，arcs[i][j]表示弧 <vi, vj>上的权值。若<vi, vj>不存在，则置arcs[i][j]为∞（在计算机上可 用允许的最大值代替）。S为已找到从v出发的最短路径的终点集合，它 的初始状态为空集。那么，从v出发到图上其余各顶点（终点）vi可能达 到的最短路径长度的初值为： D[i] = arcs[Locate Vex(G, v)][i] vi∈V 2．选择vj，使得 D[j] = Min{D[i] | vi∈V-S} vj就是当前求得的一条从v出发的最短路径的终点。令S = S ∪{j}。 3．修改从v出发到集合V－S上任一顶点vk可达的最短路径长度。如果 D[j] + arcs[j][k] < D[k] 则修改D[k]为 D[k] = D[j] + arcs[j][k] 4．重复操作2、3共n－1次。由此求得从v到图上其余各顶点的最短 路径是依路径长度递增的序列。

64 （2）算法实现： 算法7.13如下: void ShortestPath_DIJ (MGraph G, int v0, PathMatrix &P, ShortPathTable &D) { //用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及其带权长 //度D[v]。若P[v][w]为TRUE，则w是从v0到v当前求得最短路径上的顶点。 //final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径。 for (v = 0; v < G.vexnum; ++ v) { final[v] = FALSE; D[v] = G.arcs[v0][v]; for (w = 0; w < G.vexnum; ++ w) P[v][w] = FALSE; //设空路径 if (D[v]< INFINITY) { P[v][v0] = TRUE; P[v][v] = TRUE; } // if } // for D[v0] = 0; //初始化，v0顶点属于S集 final[v] = TRUE;

65 //开始主循环，每次求得v0到某个顶点v的最短路径，并加v到S集
for (i = 1; v < G.vexnum; ++ i) { //其余G.vexnum－1个顶点 min = INFINITY; //当前所知离v0顶点的最近距离 for (w = 0; v < G.vexnum; ++ w) if (!final[w]) //w顶点在V－S中 if (D[v]< min) { //w顶点离v0顶点更近 v = w; min = D[v]; } final [v] = TRUE; //离v0顶点最近的v加入S集 for (w = 0; v < G.vexnum; ++ w) //更新当前最短路径及距离 if (!final[w] & & (min + G.arcs[v][w] < D[w])) { //修改D[w]P[w]，w∈V－S D[w] = min + G.arcs[v][w]; P[w] = P[v]; P[w][w] = TRUE; } // if } // for } // ShortestPath_DIJ 时间复杂度：O(n2)。

66 （3）例子 100 V5 V0 V4 V2 V1 V3 30 60 10 5 20 50 图7.24的带权邻接矩阵 图 带权有向图

67 若对图7.24施行Dijkstra算法，则所得从V0到其余各顶点的最短路径 以及运算过程中D向量的变化情况，如下所示：
{v0, v2} {v0, v2, v4} {v0, v2, v3, v4}{v0, v2, v3, v4,v5} 从v0到各终点的D值和最短路径的求解过程 终点 i = i = i = i = i = 5 ∞ ∞ ∞ ∞ ∞ 无 10 (v0, v2) ∞ (v0, v2, v3) (v0, v4, v3) (v0, v4) (v0, v4) v1 v2 v3 v4 v5 vj S (v0, v5) (v0, v5) (v0, v4, v5) (v0, v4, v3, v5) v v v v5

68 ￡7.6.2 每一对顶点之间的最短路径 （1）基于Dijkstra算法的算法
每次以一个顶点为源点，重复执行Dijkstra算法n次。这样，便可求 得每一对顶点之间的最短路径。总的执行时间为O(n3) 。 （2）Floyd（弗洛伊德）算法 ①算法思想： 假设求从顶点vi到vj的最短路径。如果从vi到vj有弧，则从vi到vj存在一条长度为arxs[i][j]的路径，该路径不一定是最短路径，尚需进行n次试探。 1．考虑路径(vi, v0, vj)是否存在(即叛别弧(vi, v0)和(v0, vj)是否存在)。如果 存在，则比较(vi, vj)和(vi, v0, vj)的路径长度，取长度较短者为从vi到vj的中间顶 点的序号不大于0的最短路径。 2．在路径上再增加一个顶点v1，也就是说，如果(vi, … , v1)和(v1, … , vj)分 别是当前找到的终结顶点的序号不大于0的最短路径，那么(vi, … , v1, … , vj)就 有可能是从vi到vj的终结顶点的序号不大于1的最短路径。 3．将它和语句得到的从vi到vj中间顶点序号不大于0的最短路径相比较, 从 中选出中间顶点的序号不大于1的最短路径之后，再增加一个顶点v2，继续进 行试探。 4．依次类推。经过n次比较后，最后求得的必是从vi到vj的最短路径。 一般，若(vi, … , vk)和(vk, … , vj)分别是从vi到vk和从vk到vj的中间顶点的序 号不大于k-1的最短路径，则将(vi, … , vk, … , vj)和已经得到的从vi到vj且中间 顶点序号不大于k-1的最短路径相比较，其长度较短者便是从vi到vj的中间顶点 的序号不大于k的最短路径。

69 ②算法实现 为实现Floyd算法，定义一个n阶方阵序列： D(-1), D(0), D(1), … , D(k), … ,D(n-1) 其中： D(-1)[i][j] = G.arcs[i][j] D(k) [i][j] = Min {D(k-1) [i][j], D(k-1) [i][k] + D(k-1) [k][j]} 0≤k≤n－1 D(1)[i][j]是从vi到vj的中间顶点的序号不大于1的最短路径的长度；D(k) [i][j] 从vi到vj的中间顶点的序号不大于k的最短路径的长度；D(n-1) [i][j]就是从vi到vj 的最短路径的长度。 算法7.14如下: void ShortestPath_FLOYD (MGraph G, int v0, PathMatrix &P[ ], DistancMatrix &D) { //用Floyd算法求有向网G中各对顶点v和w的最短路径P[v][w]及其带权长度 // D[v][w]。若P[v][w][u]为TRUE，则u是从v到w当前求得最短路径上的顶点。 for (v = 0; v < G.vexnum; ++ v) //各对结点之间初始已知路径及距离 for (w = 0; w < G.vexnum; ++ w) { D[v][w] = G.arcs[v][w]; for (u = 0; u < G.vexnum; ++ u) P[v][w][u] = FALSE; if (D[v][w] < INFINITY) { //从v到w有直接路径 P[v][w][v] = TRUE; P[v][w][w] = TRUE; } // if } // for

70 时间复杂度：O(n3)。 for (u = 0; u < G.vexnum; ++ u) for (v = 0; v < G.vexnum; ++ v) for (w = 0; w < G.vexnum; ++ w) if (D[v][u] + D[u][w] < D[v][w]) { //从v经u到w的一条路径更短 D[v][w] ＝ D[v][u] + D[u][w]； for (i = 0; i < G.vexnum; ++ i) P[v][w][i] = P[v][u][i] | | P[u][w][i]; } // if } // ShortestPath_FLOYD ③例子 例如，利用Floyd算法，可求得图7.25(a)所示带权有向图的每一对顶点之 间的最短路径及其路径长度如图7.26所示。 V0 V2 V1 4 a 11 b 6 2 c 3 ∞ (b) 邻接矩阵 (a) 有向网 图7.25 带权有向图

71 P(-1) P(0) P(1) P(2) D(-1) D(0) D(1) D(2) D P ∞ 1 2 0 AB AC AB AC AB ABC AB ABC BA BC BA BC BA BC BCA BC CA CA CAB CA CAB CA CAB 图7.26 图7.25中有向图的各对顶点间的最短路径及其路径长度