第七章 图

7.1 抽象数据类型图的定义 7.2 图的存储表示 7.3 图的遍历 7.4 最小生成树 7.5 重（双）连通图和关节点 7.6 两点之间的最短路径问题 7.7 拓扑排序 7.8 关键路径

图是由一个顶点集 V 和一个弧集 R构成的数据结构。 图的结构定义: 图是由一个顶点集 V 和一个弧集 R构成的数据结构。 Graph = (V, R ) 其中，VR＝{<v,w>| v,w∈V 且 P(v,w)} <v,w>表示从 v 到 w 的一条弧，并称 v 为弧头，w 为弧尾。 谓词 P(v,w) 定义了弧 <v,w>的意义或信息。

由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图。 例如: G1 = (V1, VR1) 其中 V1={A, B, C, D, E} VR1={<A,B>, <A,E>, <B,C>, <C,D>, <D,B>, <D,A>, <E,C> } E A C B D

若<v, w>VR 必有<w, v>VR, 则称 (v,w) 为顶点 v 和顶点 w 之间存在一条边。 由顶点集和边集构成的图称作无向图。 若<v, w>VR 必有<w, v>VR, 则称 (v,w) 为顶点 v 和顶点 w 之间存在一条边。 例如: G2=(V2,VR2) V2={A, B, C, D, E, F} VR2={(A, B), (A, E), (B, E), (C, D), (D, F), (B, F), (C, F) } B C A F E D

名词和术语 网、子图 完全图、稀疏图、稠密图 邻接点、度、入度、出度 路径、路径长度、简单路径、简单回路 连通图、连通分量、 强连通图、强连通分量 生成树、生成森林

弧或边带权的图分别称作有向网或无向网。 A B E C F B A E B C 设图G=(V,{VR}) 和图 G=(V,{VR}), 9 15 11 7 21 3 2 B 设图G=(V,{VR}) 和图 G=(V,{VR}), 且 VV, VRVR, 则称 G 为 G 的子图。 A E B C

假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完全图; 含有 e=n(n-1) 条弧的有向图称作 有向完全图; 若边或弧的个数 e<nlogn，则称作稀疏图，否则称作稠密图。

假若顶点v 和顶点w 之间存在一条边， 则称顶点v 和w 互为邻接点， 边(v,w) 和顶点v 和w 相关联。 和顶点v 关联的边的数目定义为边的度。 A C D F E B 例如: 右侧图中 ID(B) = 3 ID(A) = 2

对有向图来说， A B E C F 顶点的出度: 以顶点v 为弧尾的弧的数目; 顶点的入度: 以顶点v为弧头的弧的数目。 例如: 由于弧有方向性，则有入度和出度之分 A B E C F 顶点的出度: 以顶点v 为弧尾的弧的数目; 顶点的入度: 以顶点v为弧头的弧的数目。 例如: OD(B) = 1 顶点的度(TD)= 出度(OD)+入度(ID) ID(B) = 2 TD(B) = 3

设图G=(V,{VR})中的一个顶点序列 { u=vi,0,vi,1, …, vi,m=w}中，(vi,j-1,vi,j)VR 1≤j≤m, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边的数目称作路径长度。 如:从A到F长度为 3 的路径{A,B,C,F} 简单路径:指序列中顶点不重复出现的路径。 A B E C F 简单回路:指序列中第一个顶点和最后一个顶点相同的路径。

若图G中任意两个顶点之间都有路径相通，则称此图为连通图; B A C D F E B A C D F E 若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量。

若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图。 对有向图， 否则，其各个强连通子图称作它的强连通分量。 A B E C F A B E C F

假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树。 对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林。 B A C D F E

基本操作 结构的建立和销毁 对顶点的访问操作 插入或删除顶点 插入和删除弧 对邻接点的操作 遍历

结构的建立和销毁 CreatGraph(&G, V, VR): // 按定义(V, VR) 构造图 DestroyGraph(&G): // 销毁图

对顶点的访问操作 LocateVex(G, u); // 若G中存在顶点u，则返回该顶点在 // 图中“位置” ；否则返回其它信息。 GetVex(G, v); // 返回 v 的值。 PutVex(&G, v, value); // 对 v 赋值value。

对邻接点的操作 FirstAdjVex(G, v); NextAdjVex(G, v, w); // 点”。若 w 是 v 的最后一个邻接点，则 // 返回“空”。

插入或删除顶点 InsertVex(&G, v); //在图G中增添新顶点v。 DeleteVex(&G, v);

插入和删除弧 InsertArc(&G, v, w); // 在G中增添弧<v,w>，若G是无向的， //则还增添对称弧<w,v>。 DeleteArc(&G, v, w); //在G中删除弧<v,w>，若G是无向的， //则还删除对称弧<w,v>。

遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 遍 历 DFSTraverse(G, v, Visit()); //从顶点v起深度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。 BFSTraverse(G, v, Visit()); //从顶点v起广度优先遍历图G，并对每 //个顶点调用函数Visit一次且仅一次。

7.2 图的存储表示 一、图的数组(邻接矩阵)存储表示 二、图的邻接表存储表示 三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示

一、图的数组(邻接矩阵)存储表示 定义:矩阵的元素为 Aij={ 0 (i,j)VR 1 (i,j)VR B A C D F E

有向图的邻接矩阵为非对称矩阵 A B E C F

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;

A 1 4 B 0 4 5 C 3 5 D 2 5 E 0 1 F 1 2 3 二、图的邻接表 存储表示 0 1 2 3 4 5 D B A

有向图的邻接表 A B E C F 1 4 2 3 0 1 0 1 2 3 4 A B C D E  可见，在有向图的邻接表中不易找到指向该顶点的弧

A B E C D 有向图的逆邻接表 在有向图的邻接表中，对每个顶点，链接的是指向该顶点的弧 A B C D E 3 4 2  1

弧的结点结构 adjvex nextarc info typedef struct ArcNode { int adjvex; // 该弧所指向的顶点的位置 struct ArcNode *nextarc; // 指向下一条弧的指针 InfoType *info; // 该弧相关信息的指针 } ArcNode;

顶点的结点结构 data firstarc typedef struct VNode { VertexType data; // 顶点信息 ArcNode *firstarc; // 指向第一条依附该顶点的弧 } VNode, AdjList[MAX_VERTEX_NUM];

图的结构定义(邻接表) typedef struct { AdjList vertices; int vexnum, arcnum; int kind; // 图的种类标志 } ALGraph;

三、有向图的十字链表存储表示 A B C A B C 2 1 ∧ 2 0 ∧ ∧ 0 2 ∧ ∧ 0 1 0 1 2 ∧

弧的结点结构 tailvex headvex hlink tlink info 弧尾顶点位置 弧头顶点位置 弧的相关信息 弧尾顶点位置 弧头顶点位置 弧的相关信息 指向下一个有相同弧头的结点 指向下一个有相同弧尾的结点 typedef struct ArcBox { // 弧的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; } VexNode;

typedef struct VexNode { // 顶点的结构表示 VertexType data; 顶点的结点结构 data firstin firstout 顶点信息数据 指向该顶点的第一条入弧 指向该顶点的第一条出弧 typedef struct VexNode { // 顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; } VexNode;

有向图的结构表示(十字链表) typedef struct { VexNode xlist[MAX_VERTEX_NUM]; // 顶点结点(表头向量) int vexnum, arcnum; //有向图的当前顶点数和弧数 } OLGraph;

四、无向图的邻接多重表存储表示 边的结构表示 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;

7.3 图的遍历 深度优先搜索 广度优先搜索 遍历应用举例 从图中某个顶点出发游历图，访遍 图中其余顶点，并且使图中的每个顶点 仅被访问一次的过程。 深度优先搜索 广度优先搜索 遍历应用举例

一、深度优先搜索遍历图 连通图的深度优先搜索遍历 从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。

W1、W2和W3 均为 V 的邻接点，SG1、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。 V for (W1、W2、W3 ) 若该邻接点W未被访问， 则从它出发进行深度优先搜索遍历。

从上页的图解可见: 1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历; 2. 如何判别V的邻接点是否被访问？ 解决的办法是:为每个顶点设立一个 “访问标志 visited[w]”;

void DFS(Graph G, int v) { // 从顶点v出发，深度优先搜索遍历连通图 G visited[v] = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w)) if (!visited[w]) DFS(G, w); // 对v的尚未访问的邻接顶点w // 递归调用DFS } // DFS

非连通图的深度优先搜索遍历 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。

void DFSTraverse(Graph G, Status (*Visit)(int v)) { // 对图 G 作深度优先遍历。 VisitFunc = Visit; for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; // 访问标志数组初始化 if (!visited[v]) DFS(G, v); // 对尚未访问的顶点调用DFS }

a a b c h d e k f g c a b g h c d e f d k h k f e a c h d k f e b g 例如: a a b c h d e k f g 8 1 2 3 4 5 6 7 c a b g h c d e f d k h k f e F F F F F F F F F 0 1 2 3 4 5 6 7 8 访问标志: T T T T T T T T T 访问次序: a c h d k f e b g

二、广度优先搜索遍历图 对连通图，从起始点V到其余各顶点必定存在路径。 其中，V->w1, V->w2, V->w8 V 的路径长度为1; V w3 w7 V->w7, V->w3, V->w5 的路径长度为2; w8 w4 w6 V->w6, V->w4 的路径长度为3。 w5

从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

… … Status (*Visit)(int v)){ for (v=0; v<G.vexnum; ++v) void BFSTraverse(Graph G, Status (*Visit)(int v)){ for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; //初始化访问标志 InitQueue(Q); // 置空的辅助队列Q for ( v=0; v<G.vexnum; ++v ) if ( !visited[v]) { // v 尚未访问 } } // BFSTraverse … …

visited[v] = TRUE; Visit(v); // 访问u 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]) { visited[w]=TRUE; Visit(w); EnQueue(Q, w); // 访问的顶点w入队列 } // if } // while

三、遍历应用举例 1. 求一条从顶点 i 到顶点 s 的 简单路径 2. 求两个顶点之间的一条路径 长度最短的路径

1. 求一条从顶点 i 到顶点 s 的简单路径 a b c h d e k f g 求从顶点 b 到顶点 k 的一条简单路径。 例如: b c h d a e k f g 假设找到的第一个邻接点是a,且得到的结点访问序列为: b a d h c e k f g

结论: 1. 从顶点 i 到顶点 s ,若存在路径，则从顶点 i 出发进行深度优先搜索，必能搜索到顶点 s 。 2. 遍历过程中搜索到的顶点不一定是路径上的顶点。 3. 由它出发进行的深度优先遍历已经完成的顶点不是路径上的顶点。

void DFSearch( int v, int s, char *PATH) { // 从第v个顶点出发递归地深度优先遍历图G， // 求得一条从v到s的简单路径，并记录在PATH中 visited[v] = TRUE; // 访问第 v 个顶点 for (w=FirstAdjVex(v); w!=0 ; w=NextAdjVex(v) ) if (!visited[w]) DFSearch(w, s, PATH); } Append(PATH, getVertex(v)); // 第v个顶点加入路径 &&!found if (w=s) { found = TRUE; Append(PATH, w); } else if (!found) Delete (PATH); // 从路径上删除顶点 v

2. 求两个顶点之间的一条路径 长度最短的路径 若两个顶点之间存在多条路径，则其中必有一条路径长度最短的路径。如何求得这条路径?

深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。 例如: 深度优先搜索访问顶点的次序取决于图的存储结构，而广度优先搜索访问顶点的次序是按“路径长度”渐增的次序。 a b c h d e k f g 因此，求路径长度最短的路径可以基于广度优先搜索遍历进行，但需要修改链队列的结点结构及其入队列和出队列的算法。

链队列的状态如下所示: Q.front Q.rear 3 1 2 4 7 5 例如:求右图中顶点 3 至顶点 5 的一条最短路径。 3 2 6 8 9 链队列的状态如下所示: Q.front Q.rear 3 1 2 4 7 5

1) 将链队列的结点改为“双链”结点。即 结点中包含next 和priou两个指针; 2) 修改入队列的操作。插入新的队尾结点时，令其priou域的指针指向刚刚出队列的结点，即当前的队头指针所指结点; 3) 修改出队列的操作。出队列时，仅移 动队头指针，而不将队头结点从链表中删除。

typedef DuLinkList QueuePtr; void InitQueue(LinkQueue& Q) { Q.front = Q.rear = new QNode; Q.front->next = Q.rear->next = NULL; } void EnQueue( LinkQueue& Q, QelemType e ) { p = new QNode; p->data = e; p->next = NULL; p->priou = Q.front; Q.rear->next = p; Q.rear = p; void DeQueue( LinkQueue& Q, QelemType& e ) { Q.front = Q.front->next; e = Q.front->data

7.4 (连通网的)最小生成树 问题： 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前提下建立这个通讯网？

算法一：（普里姆算法） 算法二：（克鲁斯卡尔算法） 该问题等价于： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和”为最小。 算法一：（普里姆算法） 算法二：（克鲁斯卡尔算法）

普里姆算法的基本思想: 取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。

例如: a b c d e g f a b c e g d f 所得生成树权值和 = 14+8+3+5+16+21 = 67 19 5 14 18 27 16 8 21 3 12 7 a b 5 14 c e 8 16 3 g d 21 f 所得生成树权值和 = 14+8+3+5+16+21 = 67

一般情况下所添加的顶点应满足下列条件: 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边。 V-U U

设置一个辅助数组，对当前V－U集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边： struct { VertexType adjvex; // U集中的顶点序号 VRType lowcost; // 边的权值 } closedge[MAX_VERTEX_NUM];

例如: a b c d e g f a b c e d d c a e d e a d e a 5 5 7 12 19 3 3 8 8 14 19 m m 14 m 18 19 5 7 12 m m m 5 3 m m m m 7 3 8 21 m 14 12 m 8 m 16 m m m 21 m 27 18 m m m 16 27 a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 a b c e d d c a e d e a d e a 5 5 7 12 19 3 3 8 8 14 14 21 18 16

for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化 if (j!=k) void MiniSpanTree_P(MGraph G, VertexType u) { //用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; j<G.vexnum; ++j ) // 辅助数组初始化 if (j!=k) closedge[j] = { u, G.arcs[k][j].adj }; closedge[k].lowcost = 0; // 初始，U＝{u} for (i=0; i<G.vexnum; ++i) { } 继续向生成树上添加顶点;

k = minimum(closedge); // 求出加入生成树的下一个顶点(k) 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) closedge[j] = { G.vexs[k], G.arcs[k][j].adj };

克鲁斯卡尔算法的基本思想： 考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。 具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。

例如: a b c d e g f 19 5 14 18 27 16 8 21 3 12 7 19 a b 5 12 14 c 7 18 e 16 8 3 g d 21 f

算法描述: 构造非连通图 ST=( V,{ } ); k = i = 0; // k 计选中的边数 while (k<n-1) { 检查边集 E 中第 i 条权值最小的边(u,v); 若(u,v)加入ST后不使ST中产生回路， 则 输出边(u,v); 且 k++; }

比较两种算法 克鲁斯卡尔算法 算法名 普里姆算法 时间复杂度 O(n2) O(eloge) 适应范围 稠密图 稀疏图

7.5 重（双）连通图 和关节点 问题： 若从一个连通图中删去任何一个顶点及其相关联的边，它仍为一个连通图的话，则该连通图被称为重（双）连通图。

如何判别给定的连通图是否是双连通图？ 若连通图中的某个顶点和其相关 联的边被删去之后，该连通图被分割 成两个或两个以上的连通分量，则称 此顶点为关节点。 没有关节点的连通图为双连通图。

例如:下列连通图中， 深度优先生成树 1 a h g c b f d e a b c d e f g h 1 7 2 1 1 8 3 1 1 4 6 3 1 5 3 顶点 a 和顶点 c 是关节点

假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。 关节点有何特征？ 需借助图的深度优先生成树来分析。 假设从某个顶点V0出发对连通图进行深度优先搜索遍历，则可得到一棵深度优先生成树，树上包含图的所有顶点。

若生成树的根结点，有两个或两个以上的分支，则此顶点(生成树的根)必为关节点; 对生成树上的任意一个“顶点”，若其某棵子树的根或子树中的其它“顶点”没有和其祖先相通的回边，则该“顶点”必为关节点。

对上述两个判定准则在算法中如何实现？

1) 设V0为深度优先遍历的出发点 p = G.vertices[0].firstarc; v = p->adjvex; DFSArticul(G, v); // 从第v顶点出发深度优先搜索 if (count < G.vexnum) { // 生成树的根有至少两棵子树 printf (0, G.vertices[0].data); // 根是关节点

2) 定义函数: low(v) = Min{visited[v], low[w], visited[k] } 顶点k 是生成树上和顶点v由回边 相联接的祖先; visited记录深度优先遍历时的访问次序 若对顶点v，在生成树上存在一个子树根w, 且 low[w] ≥ visited[v] 则顶点v为关节点。

1。visited[v]的值改为遍历过程中顶点的访问次序count值; 对深度优先遍历算法作如下修改： 1。visited[v]的值改为遍历过程中顶点的访问次序count值; 2。遍历过程中求得 low[v]=Min{visited[v],low[w],visited[k]} 3。从子树遍历返回时， 判别low[w]≥visited[v]?

void DFSArticul(ALGraph G, int v0) { // 从第v0个顶点出发深度优先遍历图 G, // 查找并输出关节点 } // DFSArticul min =visited[v0] = ++count; // v0是第count个访问的顶点, 并设low[v0]的初值为min for(p=G.vertices[v0].firstarc; p; p=p->nextarc) { } // 检查v0的每个邻接点 low[v0] = min;

if (visited[w] == 0) { // w未曾被访问 DFSArticul(G, w); // 返回前求得low[w] w = p->adjvex; // w为v0的邻接顶点 if (visited[w] == 0) { // w未曾被访问 DFSArticul(G, w); // 返回前求得low[w] } else // w是回边上的顶点 if (low[w] < min) min = low[w]; if (low[w]>=visited[v0]) printf(v0, G.vertices[v0].data); //输出关节点 if (visited[w] < min) min = visited[w];

7.6 两点之间的 最短路径问题 求从某个源点到其余各点的最短路径 每一对顶点之间的最短路径

求从源点到其余各点的最短路径的算法的基本思想: 依最短路径的长度递增的次序求得各条路径 v1 其中，从源点到顶点v的最短路径是所有最短路径中长度最短者。 v2 … 源点

路径长度最短的最短路径的特点: 在这条路径上，必定只含一条弧，并且这条弧的权值最小。 下一条路径长度次短的最短路径的特点: 它只可能有两种情况:或者是直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)。

再下一条路径长度次短的最短路径的特点: 它可能有三种情况：或者是，直接从源点到该点(只含一条弧)； 或者是，从源点经过顶点v1，再到达该顶点(由两条弧组成)；或者是，从源点经过顶点v2，再到达该顶点。 其余最短路径的特点： 它或者是直接从源点到该点(只含一条弧)； 或者是，从源点经过已求得最短路径的顶点，再到达该顶点。

设置辅助数组Dist，其中每个分量Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。 求最短路径的迪杰斯特拉算法： 设置辅助数组Dist，其中每个分量Dist[k] 表示 当前所求得的从源点到其余各顶点 k 的最短路径。 一般情况下， Dist[k] = <源点到顶点 k 的弧上的权值> 或者 = <源点到其它顶点的路径长度> + <其它顶点到顶点 k 的弧上的权值>

1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。 V0和k之间存在弧 V0和k之间不存在弧 其中的最小值即为最短路径的长度。 2）修改其它各顶点的Dist[k]值。 假设求得最短路径的顶点为u， 若 Dist[u]+G.arcs[u][k]<Dist[k] 则将 Dist[k] 改为 Dist[u]+G.arcs[u][k]

从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径 求每一对顶点之间的最短路径 弗洛伊德算法的基本思想是： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径

… 若<vi,vj>存在，则存在路径{vi,vj} // 路径中不含其它顶点 若<vi,v1>,<v1,vj>存在，则存在路径{vi,v1,vj} // 路径中所含顶点序号不大于1 若{vi,…,v2}, {v2,…,vj}存在， 则存在一条路径{vi, …, v2, …vj} // 路径中所含顶点序号不大于2 … 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。

7.7 拓扑排序 问题: 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。

何谓“拓扑排序”？ 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。 对有向图进行如下操作: 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。

由此所得顶点的线性序列称之为拓扑有序序列 例如：对于下列有向图 B D A C 可求得拓扑有序序列： A B C D 或 A C B D

反之，对于下列有向图 B D A C 不能求得它的拓扑有序序列。 因为图中存在一个回路 {B, C, D}

如何进行拓扑排序？ 一、从有向图中选取一个没有前驱 的顶点，并输出之; 二、从有向图中删去此顶点以及所 有以它为尾的弧; 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。

a b h c d g f e 在算法中需要用定量的描述替代定性的概念 a b c g h d f e 没有前驱的顶点  入度为零的顶点 删除顶点及以它为尾的弧  弧头顶点的入度减1

算法描述 取入度为零的顶点v; while (v<>0) { printf(v); ++m; w:=FirstAdj(v); while (w<>0) { inDegree[w]--; w:=nextAdj(v,w); } 取下一个入度为零的顶点v; if m<n printf(“图中有回路”); 算法描述

为避免每次都要搜索入度为零的顶点， 在算法中设置一个“栈”，以保存“入度为零”的顶点。 CountInDegree(G,indegree); //对各顶点求入度 InitStack(S); for ( i=0; i<G.vexnum; ++i) if (!indegree[i]) Push(S, i); //入度为零的顶点入栈

count=0; //对输出顶点计数 while (!EmptyStack(S)) { Pop(S, v); ++count; printf(v); for (w=FirstAdj(v); w; w=NextAdj(G,v,w)){ --indegree(w); // 弧头顶点的入度减一 if (!indegree[w]) Push(S, w); //新产生的入度为零的顶点入栈 } if (count<G.vexnum) printf(“图中有回路”)

7.8 关键路径 问题: 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。 问：哪些子工程项是“关键工程”？ 7.8 关键路径 问题: 假设以有向网表示一个施工流图，弧上的权值表示完成该项子工程所需时间。 问：哪些子工程项是“关键工程”？ 即：哪些子工程项将影响整个工程的完成期限的。

例如: 整个工程完成的时间为：从有向图的源点到汇点的最长路径。 汇点 a b c d e f g h k 6 4 5 2 1 8 7 6 1 “关键活动”指的是：该弧上的权值增加 将使有向图上的最长路径的长度增加。

如何求关键活动？ 什么是“关键活动” ？ 该活动的最早开始时间 = 该活动的最迟开始时间 dut i j

“事件(顶点)” 的 最早发生时间 ve(j) ve(j) = 从源点到顶点j的最长路径长度; “事件(顶点)” 的 最迟发生时间 vl(k) vl(k) = 从顶点k到汇点的最短路径长度;

假设第 i 条弧为 <j, k> 则 对第 i 项活动言 “活动(弧)”的 最早开始时间 ee(i) ee(i) = ve(j); “活动(弧)”的 最迟开始时间 el(i) el(i) = vl(k) – dut(<j,k>);

事件发生时间的计算公式: ve(源点) = 0; ve(k) = Max{ve(j) + dut(<j, k>)} vl(汇点) = ve(汇点); vl(j) = Min{vl(k) – dut(<j, k>)}

a b c d e f g h k 6 4 5 2 1 8 7 6 4 5 5 7 7 15 14 11 18 18 18 6 6 18 18 8 8 18 7 18 10 16 18 18 14 18 拓扑有序序列: a - d - f - c - b - e - h - g - k

6 4 5 7 15 14 18 16 10 8 6 4 5 7 7 7 15 14 2 3 6 6 8 8 7 10 16 14

算法的实现要点: 而 求vl的顺序应该是按拓扑逆序的次序; 显然，求ve的顺序应该是按拓扑有序的次序; 因为 拓扑逆序序列即为拓扑有序序列的 因为 拓扑逆序序列即为拓扑有序序列的 逆序列， 因此 应该在拓扑排序的过程中， 另设一个“栈”记下拓扑有序序列。

　1. 熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。 　2. 熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度优先搜索和广度优先搜索的算法。 在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。

　 3. 应用图的遍历算法求解各种简单路径问题。 　　4. 理解教科书中讨论的各种图的算法。

本章作业 7.22, 7.23, 7.27, 4.28