1、第七章第七章 图图三亚学院理工分院三亚学院理工分院伍添秀伍添秀Email:Email:（公共邮箱）（公共邮箱）2023-5-92数数据据结结构构 线性线性-表：每个元素有一个直接前趋和一直接后继非线性非线性 每一层元素可能和下层中的多个元素相关，但只能和上一层中的一个 元素相关 数据元素之间的关系是任意的树：图：1.熟悉图的各种熟悉图的各种存储结构存储结构及其及其构造算法构造算法，了解实际问题的求解效，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。率与采用何种存储结构和算法有密切联系。2.熟练掌握图的两种搜索路径的熟练掌握图的两种搜索路径的遍历遍历：深度优先搜索和广度优先：深度优先
2、搜索和广度优先搜索的算法。搜索的算法。3.图的算法应用。图的算法应用。学习提要学习提要7.1 7.1 图的定义和术语图的定义和术语7.2 7.2 图的存储结构图的存储结构7.3 7.3 图的遍历图的遍历7.4 7.4 图的连通性问题图的连通性问题7.5 7.5 有向无环图及其应用有向无环图及其应用7.6 7.6 最短路径最短路径基本内容：基本内容：7.1 图的定义和术语图的定义和术语 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集 R构成的数据结构成的数据结构。构。Graph=(V,R)R=VR其中，VR|v,wV 且 P(v,w)表示从 v 到 w 的一条弧，并称 v 为弧尾弧尾
3、，w 为弧头弧头。谓词 P(v,w)定义了弧 的意义或信息。图的结构定义图的结构定义:由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图有向图。AB E C D例如例如:G1=(V1,VR1)其中：V1=A,B,C,D,EVR1=,始点 终点由顶点集和边集构成的图称作无向图无向图。代表一条边的偶对是无序的，（V1,V2）和（V2,V1）代表同一条边。B CA D F E例如:G2=(V2,VR2)V2=A,B,C,D,E,FVR2=,结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧基
4、本操作基本操作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);/返回 v 的“第一个邻接点第一个邻接点”。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(G,v,w);/返回 v 的（相
5、对于 w 的）“下一个邻接点下一个邻接点”。/若 w 是 v 的最后一个邻接点，则返回“空”。插入或删除顶点插入或删除顶点InsertVex(&G,v);/在图G中增添新顶点v。DeleteVex(&G,v);/删除G中顶点v及其相关的弧。插入和删除弧插入和删除弧InsertArc(&G,v,w);/在G中增添弧，若G是无向的，/则还增添对称弧。DeleteArc(&G,v,w);/在G中删除弧，若G是无向的，/则还删除对称弧。遍遍 历历DFSTraverse(G,v,Visit();/从顶点v起深度优先深度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G
6、,v,Visit();/从顶点v起广度优先广度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。AEFBBC设图G=(V,VR)和图 G=(V,VR),且 VV,VRVR,则称 G为 G 的子图子图。ABECF1597211132 弧或边带权的图分别称作有向网有向网或无向网无向网。名词和术语名词和术语网、子图网、子图 假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完全图完全图；含有 e=n(n-1)条弧的有向图称作 有向完全图有向完全图；若边或弧的个数 enlogn，则称作稀疏图稀疏图，否则称作稠密图稠密图。完全图完全图、稀疏图、稠密图稀疏图、稠密
7、图 假若顶点v 和顶点w 之间存在一条边，则称顶点v 和w 互为邻接点邻接点，例如例如:ID(B)=3ID(A)=2 边(v,w)和顶点v 和w 相关联关联。和顶点v 关联的边的数目边的数目定义为顶点v的度度。ACDFEB邻接点、度、入度、出度邻接点、度、入度、出度顶点的出度出度:以顶点v为弧尾的弧的数目；ABECF对有向图来说对有向图来说，顶点的入度入度:以顶点v为弧头的弧的数目。顶点的度度(TD)=)=出度出度(OD)+)+入度入度(ID)例如例如:ID(B)=2OD(B)=1TD(B)=3 设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1,vi,m=w中，(vi,j-1,vi
8、,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECF如如:长度为3的路径A,B,C,F简单路径简单路径:序列中顶点不重复出现的路径。简单回路简单回路:序列中第一个顶点和最后一个顶点相同的路径。路径、路径长度、简单路径路径、路径长度、简单路径、简单回路简单回路 若图G中任意两个顶点之间都有路径相通，则称此图为连通图连通图；若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量连通分量。BACDFEBACDFE连通图、连通分量、强连通图、强连通分量连通图、连通分量、强连通图、强连通分量 对有向图，对有向图，若任意两个顶点之间都存在一
9、条有向路径，则称此有向图为强连通图强连通图。ABDCEABDCE否则，其各个强连通子图称作它的强连通分量强连通分量。假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树生成树。对非连通图，则称由各个连通分量的生成树构成的集合为此非连通图的生成森生成森林林。BACDFE生成树、生成森林生成树、生成森林7.2 图的存储结构图的存储结构7.2.1 数组表示方法数组表示方法7.2.2 邻接表邻接表Aij=0 (i,j)VR1 (i,j)VR7.2.1 7.2.1 数组表示方法数组表示方法BACDFE定义定义:邻接矩阵的元素为
10、邻接矩阵的元素为010010100011000101001001110000011100 用两个数组分别存储数据元素（顶点）和数据用两个数组分别存储数据元素（顶点）和数据元素之间的关系（边或弧）的信息。元素之间的关系（边或弧）的信息。无向图的邻接矩阵一定是无向图的邻接矩阵一定是对称矩阵对称矩阵，而有向，而有向图的邻接矩阵则不一定为图的邻接矩阵则不一定为非对称矩阵非对称矩阵。ABECD0 1 0 0 10 0 1 0 00 0 0 1 01 1 0 0 00 0 1 0 0 网的邻接矩阵可定义为：网的邻接矩阵可定义为：Aij=否则Wi,j 若(i,j)或VRABECD56384260 560 2
11、0 64 8040/-/-图的数组（邻接矩阵）存储表示图的数组（邻接矩阵）存储表示-#define INFINITY INF_MAX /#define INFINITY INF_MAX /最大值最大值#define MAX_VERTEX_NUM 20 /MAX_VERTEX_NUM 20 /最大顶点个数最大顶点个数Typedef enumDG,DN,UDG,UDN GraphKindTypedef enumDG,DN,UDG,UDN GraphKind;/;/有向图、有向图、/有向网、无向图、无向网有向网、无向图、无向网 typedef struct ArcCell /弧的定义弧的定义 VRT
12、ype adj;/VRType是顶点关系类型。对无权图，用1 /或0表示相邻否；对带权图，则为权值类型。InfoType *info;/该弧相关信息的指针 ArcCell，AdjMatrixMAX_VERTEX_NUM MAX_VERTEX_NUM;typedef struct /图的定义图的定义 VertexType vexsMAX_VERTEX_NUM;/顶点向量 AdjMatrix arcs;/邻接矩阵 int vexnum,arcnum;/图的当前顶点数和弧数 GraphKind kind;/图的种类标志 MGraph;typedef struct ArcNode int adjvex
13、;/该弧所指向的顶点的位置 struct ArcNode *nextarc;/指向下一条弧的指针 InfoType *info;/该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构7.2.2 邻接表邻接表typedef struct VNode VertexType data;/顶点信息 ArcNode *firstarc;/指向第一条依附该顶点的弧 VNode,AdjListMAX_VERTEX_NUM;顶点的结点结构顶点的结点结构 data firstarctypedef struct AdjList vertices;int vexnum,
14、arcnum;/图的当前顶点数和弧数 int kind;/图的种类标志 ALGraph;图的结构定义图的结构定义0 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE无向图的邻接表无向图的邻接表有向图的邻接表有向图的邻接表1 4230 120 1 2 3 4 A B C D EABECD 可见，在有向图的邻接表中不易找到指向该顶点的弧。ABECD有向图的逆邻接表有向图的逆邻接表 在有向图的逆邻接表中，对每个顶点，链接的是指向该顶点的弧。A B C D E 303420 012341 7.3 图的遍历图的遍历何谓图的遍历？何谓图的遍历？从图中某个
15、顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索（深度优先搜索（DFS）广度优先搜索（广度优先搜索（BFS）从图中某个顶点V0 出发，访问此顶点，然后依次从依次从V0的各个未被访问的邻接点出发深度优先搜的各个未被访问的邻接点出发深度优先搜索遍历图索遍历图，直至图中所有和V0有路径相通的顶点都被访问到；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直到图中所有顶点都被访问到为止。7.3.1 深度优先搜索（深度优先搜索（Depth_First Search）Vw1SG1SG2SG3W1、W2和W3 均为 V 的邻接点，SG1
16、、SG2 和 SG3 分别为含顶点W1、W2和W3 的子图。访问顶点 V：for(W1、W2、W3)若该邻接点W未被访问，则从它出发进行深度优先搜索遍历。w2w3w2 对上图，假设从v1开始进行深度优先遍历，则遍历顺序为：v1v2 v4 v8 v5 v3 v6 v7V1v2v6v3v4v5v7v8从上页的图解可见从上页的图解可见:1.深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个“访问标志 visitedw”。其初值为false，一旦某个顶点被访问，则其相应的分量置为true。2.如何判别V的邻接点是否被访问？void DFS(Graph G,int v)/从
17、顶点从顶点v出发，出发，深度优先遍历图深度优先遍历图 G G visitedv=TRUETRUE;VisitFunc(v);/访问第v个顶点 for(w=FirstAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)DFS(G,w);/对v的尚未访问的邻接顶点w，递归调用DFS/DFS算法算法 7.57.5 首先将图中每个顶点的访问标志设为 FALSE,之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。一般图的深度优先搜索遍历一般图的深度优先搜索遍历void DFSTraverse(Graph G,S
18、 Status(*Visit)(int v)/对图对图 G G 作深度优先遍历。作深度优先遍历。VisitFunc=Visit;for(v=0;vG.vexnum;+v)visitedv=FALSEFALSE;/访问标志数组初始化 for(v=0;vG.vexnum;+v)if(!visitedv)DFS(G,v);/对尚未访问的顶点调用DFS算法算法 7.47.4abchdekfgF F F F F F F F FT T T T T T T TTach d kfe bgachkfedbg访问标志访问标志:访问次序访问次序:例如例如:0 1 2 3 4 5 6 7 87.3.2 广度优先搜索广
19、度优先搜索（Breadth_First Search）从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问未被访问过的邻接点，之后按按这些顶点被访问的先后次序依次访问它们的邻接点这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。Vw1w8w3w7w6w2w5w4对连通图，从起始点V到其余各顶点必定存在路径。其中，VW1,VW2,VW8 的路径长度为1；VW7,VW3,VW5 的路径长度为2；VW6,VW4 的路径长度为3。
20、w1Vw2w7w6w3w8w5w4 对上图，假设从v1开始进行广度优先遍历，则遍历顺序为：v1v2 v3 v4 v5 v6 v7 v8V1v2v6v3v4v5v7v8 void BFSTraverse(Graph G,Status(*Visit)(int v)/按广度优先非递归遍历图按广度优先非递归遍历图G G，使用辅助队列，使用辅助队列Q Q和和/访问标志数组访问标志数组visited for(v=0;vG.vexnum;+v)visitedv=FALSEFALSE;/初始化访问标志 InitQueue(Q);/置空的辅助队列Q for(v=0;v=0;w=NextAdjVex(G,u,w)
21、if(!visitedw)/W为u的尚未访问的邻接顶点 visitedw=TRUETRUE;Visit(w);EnQueue(Q,w);/访问的顶点w入队列 /if/while7.4.1 无向图的连通分量和生成树7.4.2 有向图的强连通分量7.4.3 最小生成树7.4.4 关节点和重连通分量7.4 图的连通性问题图的连通性问题 void DFSForest(Graph G,CSTree&T)/建立无向图建立无向图G G的深度优先生成森林的的深度优先生成森林的(最左最左)孩子孩子(右右)兄弟链表兄弟链表T T T=NULL;for(v=0;vG.vexnum;+v)visitedv=FALSE
22、;for(v=0;vnextsibling=p;/是其他生成树的根是其他生成树的根(前一棵的根的前一棵的根的“兄弟兄弟”q=p;/q/q指示当前生成树的根指示当前生成树的根 DFSForest(G,v,p);/建立以建立以p p为根的生成树为根的生成树 /DFSForest7.4.1 无向图的连通分量和生成树无向图的连通分量和生成树算法算法 7.77.7void DFSTree(Graph G,CSTree&T)/从第从第v v个顶点出发深度优先遍历图个顶点出发深度优先遍历图G G，建立以，建立以T T为根的生成树。为根的生成树。visitedv=TRUE;first=TRUE;for(w=F
23、isrtAdjVex(G,v);w=0;w=NextAdjVex(G,v,w)if(!visitedw)p=(CSTree)malloc(sizeof(CSNode);/分配孩子结点分配孩子结点 *p=GetVex(G,w),NULL,NULL;if(first)/w/w是是v v的第一个未被访问的邻接顶点的第一个未被访问的邻接顶点 T-lchild=p;first=FALSE;/是根的左孩子结点是根的左孩子结点 /if else /w/w是是v v的其他未被访问的邻接顶点的其他未被访问的邻接顶点 q-nextsibling=p;/是上一邻接顶点的有兄弟结点是上一邻接顶点的有兄弟结点 /els
24、e q=p;DFSTree(G,w,q);/从第从第w w个顶点出发深度优先遍历图个顶点出发深度优先遍历图G G，建立子生成树，建立子生成树q q /if/DFSTree算法算法 7.87.8 问题：问题：7.4.3 7.4.3 最小生成树最小生成树 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在如何在最节省经费的前提下建立最节省经费的前提下建立这个通讯网通讯网？构造网的一棵最小生成树，即：在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。该问题等价于：该问题等价于：算法二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法
25、）算法一：（普里姆算法）算法一：（普里姆算法）算法利用了最小生成树的下列一种简称为MST的性质：假设N=（V，E）是一个连通网，U是顶点集V的一个非空集合。若(u,v)是一条具有最小权值（代价）的边，其中u U，vV-U，则必存在一棵包含边（u,v）的最小生成树。可用反证法证明：假设网N任何一棵最小生成树都不含(u,v)。设T是一棵最小生成树，当将边(u,v)加入到T中时，由生成树定义，T中必存在一条包含(u,v)的回路。另一方面，T是生成树，T中必存在另一条边(u,v)，其中u U，vV-U，且u和u之间，v和v之间均有路径相通，删去边(u,v)，便可消除回路，同时得到另一棵生成树T。因为（
26、u,v）的代价不高于(u,v)，则T的代价亦不高于T，T是包含(u,v)的一棵最小生成树。由此和假设矛盾。取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点在添加的顶点 w 和已经在生成树上的顶点和已经在生成树上的顶点v 之间必定存在一条边，之间必定存在一条边，并且该边的权值在所有连通顶点并且该边的权值在所有连通顶点 v 和和 w 之间的边之间的边中取值最小中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 条边为止。普里姆算法的基本思想普里姆算法的基本思想:假设N=（V，E）是连通网，TE是N上最小生成树中边的集合。算法从U=u0(u0V,TE
27、=开始，重复执行下述操作：在所有uU,vV-U的边(u,v)E中找一条代价最小的边（u0，v0）并入集合，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=（V，TE）为N的最小生成树。普里姆算法普里姆算法:abcdegf例如例如:195141827168213ae12dcbgf7148531621所得生成树权值和=14+8+3+5+16+21=67 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U，则应在所有连通在所有连通U中中顶点和顶点和V-U中顶点的边中选取权值最小的边中顶点的边中选取权值最小的边。一般情况下所
28、添加的顶点应满足下列条件:UV-UV1V2V4V3V5V66155563426（a）V1V2V4V3V5V61（b）V1V2V4V3V5V61（c）4V1V2V4V3V5V61（d）42V1V2V4V3V5V61（e）425V1V2V4V3V5V61（f）4253图图7.16 7.16 普里姆算法构造最小生成树的过程普里姆算法构造最小生成树的过程 设置一个辅助数组closedge，对当前VU集中的每个顶点，记录和顶点集U中顶点相连接的代价最小的边。对每个顶点vi V-U，在辅助数组中存在一个相应分量closedgei-1，它包括两个域，其中lowcost存储该边上的权。显然：closedgei
29、-1.lowcost=Mincost(u,v)|u Ustruct VertexType adjvex;/U集中的顶点序号 VRType lowcost;/边的权值 closedgeMAX_VERTEX_NUM;abcdegf195141827168213ae12dcb7aaa19141814例如例如:e12ee8168d3dd7213c5 5closedge0a1b2c3d4e5f6gAdjvexLowcostvoid MiniSpanTree_P(MGraph G,VertexType u)/用普里姆算法从顶点u出发构造网G的最小生成树 k=LocateVex(G,u);for(j=0;j
30、G.vexnum;+j)/辅助数组初始化 if(j!=k)closedgej=u,G.arcskj.adj;closedgek.lowcost=0;/初始，Uu for(i=0;iG.vexnum;+i)继续向生成树上添加顶点继续向生成树上添加顶点;算法算法 7.97.9 k=minimum(closedge);/求出加入生成树的下一个顶点(k)printf(closedgek.adjvex,G.vexsk);/输出生成树上一条边 closedgek.lowcost=0;/第k顶点并入U集 for(j=0;jG.vexnum;+j)/修改其它顶点的最小边 if(G.arcskj.adj clo
31、sedgej.lowcost)closedgej=G.vexsk,G.arcskj.adj;具体做法具体做法:先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使SG 中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑问题的出发点考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：V1V2V4V3V5V66155563426（a）V1V2V4V3V5V61（b）V1V2V4V3V5V61（f）4253图图7.18 7.18 克鲁斯卡尔算法构造最小生
32、成树的过程克鲁斯卡尔算法构造最小生成树的过程V1V2V4V3V5V61（d）23V1V2V4V3V5V61（e）423V1V2V4V3V5V61（c）2abcdegf195141827168213ae12dcbgf7148531621例如例如:7121819算法描述算法描述:构造非连通图 ST=(V,);k=i=0;/k 计选中的边数 while(kadjvex;DFSArticul(G,v);/从第v顶点出发深度优先搜索 if(count nextarc)void DFSArticul(ALGraph G,int v0)/从第v0个顶点出发深度优先遍历图 G,/查找并输出关节点/DFSArt
33、iculmin=visitedv0=+count;/v0是第是第count个访问的顶点个访问的顶点,并设并设lowv0的初值的初值/为为min/检查v0的每个邻接点lowv0=min;算法算法 7.107.10 w=p-adjvex;/w为v0的邻接顶点 if(visitedw=0)/w未曾被访问 DFSArticul(G,w);/返回前求得loww else /w是回边上的顶点if(loww=visitedv0)printf(v0,G.verticesv0.data);/输出关节点输出关节点if(visitedw min)min=visitedw;7.5 有向无环图及其应用有向无环图及其应用
34、 问题问题:假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。对整个工程和系统，人们关心的是两个方面的问题：一是工程能否顺利进行；二是估算整个工程完成所必需的最短时间。对应于有向图，即为进行拓扑排序拓扑排序和求关键路求关键路经经的操作。何谓何谓“拓扑排序拓扑排序”？简单地说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。如何得到有向图的一个拓扑序列？如何得到有向图的一个拓扑序列？对有向图进行如下操作：按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓
35、扑有序序列。例如：对于下列有向图BDAC可求得拓扑有序序列：A B C D 或 A C B D反之：对于下列有向图BDAC不能求得它的拓扑有序序列。因为图中存在一个回路 B,C,D如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱没有前驱的顶点，并输出之；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。后一种情况说明有向图后一种情况说明有向图中存在环。中存在环。二、从有向图中删去此顶点以及所有以它为尾的删去此顶点以及所有以它为尾的弧弧；abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱
36、的顶点=入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧=弧头顶点的入度减弧头顶点的入度减1例如，对例如，对左图的拓左图的拓扑排序过扑排序过程如下所程如下所示：示：采用邻接表作有向图的存储结构，且在头结点中增加一个存放顶点入度的数组(indegree)。为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈栈”，以保存“入度为零”的顶点。Status Topologicaisort(ALGraph G)/有向图G采用邻接表/存储结构。若G无回路，则输出G的顶点的一个拓扑序列/并返回OK，否则ERROR。FindInDegree(G,indegree);/对各顶点求入度
37、InitStack(S);/建零入度顶点栈S for(i=0;iNextarc)k=p-adjvex;/对i号顶点的每个邻接点的入度减1 if(!(-indegreek)Push(S,k);/若入度为零，则入栈 /for/whileif(countG.vexnum)return ERROR;/图中无回路else return OK;/Topologicaisort算法算法 7.127.127.5.2 关键路径关键路径问题问题:假设以有向网表示一个施工流图，其中，顶点表示事件，弧表示活动，弧上的权值表示活动的持续时间。该网络称之为AOE网络。假设以该AOE网络表示一个施工流图，则有待研究的问题是
38、：（1）完成整项工程至少需要多少时间？）完成整项工程至少需要多少时间？（2）哪些工程是影响整个工程进度的关键？）哪些工程是影响整个工程进度的关键？abcdefghk64521187244例如例如:“关键活动”指的是：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加。最长路径的长度增加。整个工程完成的时间为：从有向图的源点源点到汇点汇点的最长路径。源点汇点6174 如何求关键活动？如何求关键活动？“事件(顶点vj)”的 最早发生时间 ve(j)ve(j)=从源点到顶点Vj的最长路径长度；这个时间决定了所有以Vj为尾的弧所表示的活动的最早开始时间 “事件(顶点vk)”的 最迟发生时间 v
39、l(k)，表示在不推迟整个工程完成的前提下，事件最迟发生的时间。vl(k)=工程完成时间-从顶点Vk到汇点的最长路径长度。假设第 i 条弧为，即如下图示：则 对活动ai而言，其最早开始时间 e(i)e(i)=ve(j)；最迟开始时间 l(i)l(i)=vl(k)dut()；其中：dut()为活动ai的权（持续时间）。vjvkai 事件发生时间的计算公式：vl(汇点)=ve(汇点)；vl(i)=Minvl(jl)dut()vi1vjvit：ve(源点)=0；ve(j)=Maxve(ik)+dut()事件最早发生时间的计算公式：事件最晚发生时间的计算公式：vj1vivjs：abcdefghk645
40、21187244拓扑有序序列拓扑有序序列:a-d-f-c-b-e-h-g-ka b c d efg h kvevl0645771514181814161078660a b c d efg h kvevl06457715 14 181814161078660ab ac ad be ce df eg eh fh gk hk权权6 4 5 1 1 2 8 7 4 2 4el000645777 15 14141602366887 10 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序；而 求vl的顺序应该是按拓扑逆序拓扑逆序的次序；因为，拓扑逆序序列即为拓扑有序序列的逆逆
41、序列序列，因此，应该在拓扑排序的过程中，另设一个“栈栈”记下拓扑有序序列。求关键路径的算法求关键路径的算法:1、输入e条弧，建立AOE网的存储结构；2、从源点v0出发，令ve0=0，按拓扑有序求其余各顶点的最早发生时间vei。若得到的拓扑序列中的顶点个数小于网中顶点数，则说明网中存在环，不能求关键路径，算法终止；否则执行步骤（3）；3、从汇点vn出发，令vln-1=ven-1，按逆拓扑有序求其余各顶点的最迟发生时间vli；4、根据个顶点的ve和 vl值，求每条弧的最早开始时间e(s)和最迟开始时间l(s)。若某弧满足条件e(s)=l(s)，则为关键活动。Status TopologicalOr
42、der(ALGraph G,Stack&T)/有向网有向网G G采用邻接表存储结构，求各顶点事件的最早发生时间采用邻接表存储结构，求各顶点事件的最早发生时间veve（全局（全局变量）。变量）。/T T为拓扑序列顶点栈，为拓扑序列顶点栈，S S为零入度顶点栈为零入度顶点栈。/若若G G无回路，则用栈无回路，则用栈T T返回返回G G的一个拓扑序列，且函数值为的一个拓扑序列，且函数值为OKOK，否则为，否则为ERRORERROR。FindInDegree(G,indegree);/对各顶点求入度对各顶点求入度/indegree0.vernum-1，建零入度顶点栈建零入度顶点栈S S；InitSta
43、ck(T);count=0;ve0.G.vernum-1=0;/初始化初始化 while(!StackEmpty(S)Pop(S,j);Push(T,j);+count;/j j号顶点入号顶点入T T栈并计数栈并计数算法算法 7.137.13 for(p=G.verticesj.firstarc;p;p=p-nextarc)k=p-adjvex;/对对j j号顶点的每个邻接点的入度减号顶点的每个邻接点的入度减1 1 if(-indegreek=0)Push(S,k);/若入度减为若入度减为0 0，则入栈，则入栈 if(vej+*(p-info)vek)vek=vej+*(p-info);/fo
44、r *(p-info)=dut()/while if(countnextarc)k=p-adjvex;dut=*(p-info);/dut 算法算法 7.147.14 if(v1k-dutv1j)v1j=v1k-dut;/for for(j=0;jnextarc)k=p-adjvex;dut=*(p-info);ee=vej;e1=v1k-dut;tag=(ee=e1)?*:;printf(j,k,dut,ee,e1,tag);/输出关键活动输出关键活动 /CriticalPath7.6 最短路径最短路径n 7.6.1 从某个源点到其余各顶点的最短从某个源点到其余各顶点的最短路径路径n 7.6
45、.2 每一对顶点之间的最短路径每一对顶点之间的最短路径7.6.1 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基的算法的基本思想本思想:迪杰斯特拉（迪杰斯特拉（DijkstraDijkstra）提出提出依依路径长度递路径长度递增的次序增的次序求得各条最短路径的算法求得各条最短路径的算法。其中，从源点到顶点从源点到顶点vj的最短路径的最短路径是所有最短路径中长度最短者。源点源点v1v2 在这条路径上，必定只含一条弧，并且这条弧的权值最小。假设该顶点为Vj。下一条路径长度次短的最短路径最短路径的特点：路径长度最短
46、的最短路径最短路径的特点：它只可能有两种情况：或者是直接从源点到该点（只含一条弧）；或者是从源点经过顶点vj，再到达该顶点(由两条弧组成)。假设该顶点为V2。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设终点为x）或者是弧(v0,x)；或者是中间只经过S中的顶点而最后到达顶点x的路径。因此，在一般情况下，下一条长度次短的最短路径的长度必是：Dj=Min Di|viV-S其中，Di或者是弧(v0,vi)上的权值，或者是Dk(vkS)和弧(vk,vi)上的权值之和。根据以上分析，可以得到如下描述的算法：V0和k之间存在弧V0和k之间不存在弧=kvarcsGkDist0
47、.设置辅助数组Dist，其中每个分量Distk 表示 当前所求得的从源点到其余各顶点Vk的最短路径。Distk 初值为：1）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。2）选择vj，使得 Dj=Min Di|viV-Svj就是当前求得的一条从v0出发的最短路径的终点。令S=Sj其中的最小值即为第一条最短路径的长度其中的最小值即为第一条最短路径的长度。V0和k之间存在弧V0和k之间不存在弧=kvarcsGkDist0.3）修改从v0出发到集合V-S上其它各顶点的Distk值。若若 Distj+G.arcsjkDistk则将 Distk 改为 Distj+G.arcsjk。4）
48、重复操作（2）、（3）共n-1次。由此求得从v0到图上其余各顶点的最短路径是依路径长度递增的序列。void ShortestPath_DIJ(MGraph G,int v0,PathMatrix&P,ShortPathTable&D)/用用DijkstraDijkstra算法求有向网算法求有向网G G的的v v0 0顶点到其余顶点顶点到其余顶点v v的最短的最短/路径路径PvPv 及其带权长度及其带权长度DvDv。若。若PvwPvw 为为TRUE,TRUE,则则w w是是/从从v v0 0到到v v当前当前求得最短路径上的顶点，求得最短路径上的顶点，finalv为为TRUETRUE当当/且仅当
49、且仅当vSvS,即已经即已经求得从求得从v v0 0到到v v的最短路径的最短路径 for(v=0;vG.vexnum;+v)finalv=FALSE;Dv=G.arcsv0v;for(w=0;wG.vexnum;+w)Pvw=FALSE;/设空路径设空路径 if(DvINFINITY)Pvv0=TRUE;Pvv=TRUE;/for算法算法 7.157.15 Dv0=0;finalv0=TRUE;/初始化初始化,v0,v0顶点属于顶点属于S S集集 /开始主循环，每次求得开始主循环，每次求得v0v0到某个到某个v v顶点的最短路径，并加顶点的最短路径，并加v v到到S S集集 for(i=0;
50、iG.vexnum;+i)/其余其余G.vexnum-1G.vexnum-1个顶点个顶点 min=INFINITY;/当前所知离当前所知离v0v0顶点的最近距离顶点的最近距离 for(w=0;wG.vexnum;+w)if(!finalw)/w w顶点在顶点在V-SV-S中中 if(Dwmin)v=w;min=Dw;/w w顶点离顶点离v0v0顶点更近顶点更近 finalv=TRUE;/离离v0v0顶点最近的顶点最近的v v加入加入S S集集 for(w=0;wG.vexnum;+w)/更新当前最短路径及距离更新当前最短路径及距离 if(!finalw&(min+G.arcsvw Dw)Dw=
