《数据结构课件第七章》由会员分享，可在线阅读，更多相关《数据结构课件第七章（100页珍藏版）》请在金锄头文库上搜索。
1、7.1 抽象数据类型图的定义抽象数据类型图的定义7.2 图的存储表示图的存储表示7.3 图的遍历图的遍历7.4 最小生成树最小生成树7.5 两点之间的最短路径问题两点之间的最短路径问题7.6 拓扑排序拓扑排序7.7 关键路径关键路径 图图是由一个是由一个顶点集顶点集 V 和一个和一个弧集弧集 R构成构成的数据结构。的数据结构。 Graph = (V , R )其中，其中，R| v,wV 且且 P(v,w) 表示从表示从 v 到到 w 的一条弧，并称的一条弧，并称 v 为为弧头，弧头，w 为弧尾。为弧尾。 图的结构定义图的结构定义:VW 由于“弧”是有方向的，因此称由顶点集和弧集构成的图为有向图
2、有向图。 AB E C D例如例如: :G1 = (V1, VR1)其中V1=A, B, C, D, EVR1=, , , , , , 若若 VR 必有必有 VR, , 则称则称 (v,w) 为顶点为顶点v 和顶点和顶点 w 之间存在一条之间存在一条边边。 B CA D F E由顶点集和边由顶点集和边集构成的图称集构成的图称作作无向图无向图。例如例如: : G2=(V2,VR2)V2=A, B, C, D, E, FVR2=(A,B), (A,E), (B,E), (C,D), (D,F), (B,F), (C,F) 名词和术语名词和术语网、子图网、子图 完全图完全图、稀疏图、稠密图稀疏图、稠
3、密图邻接点、度、入度、出度邻接点、度、入度、出度路径、路径长度、简单路径路径、路径长度、简单路径、简单回路简单回路连通图、连通分量、连通图、连通分量、强连通图、强连通分量强连通图、强连通分量生成树、生成森林生成树、生成森林ABECFAEABBC设图设图G=(V,VR) 和和图图 G =(V ,VR ),且且 VV, VRVR,则称则称 G 为为 G 的的子子图图。1597211132 弧或边带权的图弧或边带权的图分别称作分别称作有向网有向网或或无向网无向网。假设图中有 n 个顶点，e 条边，则 含有 e=n(n-1)/2 条边的无向图称作完全图完全图； 含有 e=n(n-1) 条弧的有向图称作
4、 有向完全图有向完全图； 若边或弧的个数 enlogn，则称作稀疏图稀疏图，否则称作稠密图稠密图。 假若顶点假若顶点v 和顶点和顶点w 之间存在一条边，之间存在一条边，则称顶点则称顶点v 和和w 互为互为邻接点邻接点，ACDFE例如例如: :ID(B) = 3ID(A) = 2 边边(v,w) 和顶点和顶点v 和和w 相相关联关联。 和顶点和顶点v 关联的边的数目定义为顶点关联的边的数目定义为顶点v v的的度度。B顶点的出度出度: : 以顶点v为弧尾的弧的数目；ABECF对有向图来说对有向图来说，顶点的入度入度: : 以顶点v为弧头的弧的数目。顶点的度度( (TD)=)=出度出度( (OD)+
5、)+入度入度( (ID) )例如例如: :ID(B) = 2OD(B) = 1TD(B) = 3设图G=(V,VR)中的一个顶点序列 u=vi,0,vi,1, , vi,m=w中，(vi,j-1,vi,j)VR 1jm,则称从顶点u 到顶点w 之间存在一条路径路径。路径上边的数目称作路径长度路径长度。ABECF如如: :长度为3的路径A,B,C,F简单路径简单路径:序列中顶点不重复出现的路径。简单回路简单回路:序列中第一个顶点和最后一个顶点相同的路径。若图若图G G中任意两个顶中任意两个顶点之间都有路径相通点之间都有路径相通，则称此图为则称此图为连通图连通图；若无向图为非连通图，若无向图为非连
6、通图，则图中各个极大连通则图中各个极大连通子图称作此图的子图称作此图的连通连通分量分量。BACDFEBACDFE 若任意两个顶点之间都存在一条有向路径，则称此有向图为强连通图强连通图。ABECFABECF对有向图，对有向图， 否则，其各个强连通子图称作它的强连通分量强连通分量。 假设一个连通图有 n 个顶点和 e 条边，其中 n-1 条边和 n 个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树生成树。对非连通图，则称由各个连通分量的生成树的集合为此非连通图的生成森林生成森林。BACDFE结构的建立和销毁结构的建立和销毁插入或删除顶点插入或删除顶点对邻接点的操作对邻接点的操作对顶点
7、的访问操作对顶点的访问操作遍历遍历插入和删除弧插入和删除弧基本操作基本操作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 的“第一个邻接点第一个邻
8、接点” 。若该顶点/在 G 中没有邻接点，则返回“空”。NextAdjVex(G, v, w); / 返回 v 的（相对于 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是无向的， /则还删除对称弧。遍遍 历历DF
9、STraverse(G, v, Visit(); /从顶点v起深度优先深度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。BFSTraverse(G, v, Visit(); /从顶点v起广度优先广度优先遍历图G，并对每/个顶点调用函数Visit一次且仅一次。7.2 图的存储表示图的存储表示一、一、图的数组(邻接矩阵)存储表示二、图的邻接表存储表示三、有向图的十字链表存储表示 四、无向图的邻接多重表存储表示Aij=0 (i,j)VR1 (i,j)VR一、一、图的数组(邻接矩阵)存储表示BACDFE定义定义:矩阵的元素为矩阵的元素为无向图的邻接矩阵为对称矩阵无向图的邻接矩阵为对称矩阵
10、A B C D E FABCDEF有向图的邻接矩阵为非对称矩阵有向图的邻接矩阵为非对称矩阵ABDCEA B C D EABCDE邻接矩阵表示法特点：邻接矩阵表示法特点：1 1）无向图邻接矩阵是对称矩阵，同一条边表示了两次；）无向图邻接矩阵是对称矩阵，同一条边表示了两次；2 2）顶点）顶点v v的度：在无向图中等于二维数组对应行（或列）的度：在无向图中等于二维数组对应行（或列）中中1 1的个数；在有向图中的个数；在有向图中, , 统计第统计第 i i 行行 1 1 的个数可得的个数可得顶点顶点 i i 的出度，统计第的出度，统计第 j j 列列 1 1 的个数可得顶点的个数可得顶点 j j 的的
11、入度。入度。3 3）判断两顶点）判断两顶点v v、u u是否为邻接点：只需判二维数组对应是否为邻接点：只需判二维数组对应分量是否为分量是否为1 1；4 4）顶点不变，在图中增加、删除边：只需对二维数组对顶点不变，在图中增加、删除边：只需对二维数组对应分量赋值应分量赋值1 1或清或清0 0；5 5）设存储顶点的一维数组大小为）设存储顶点的一维数组大小为n(n(图的顶点数图的顶点数n), Gn), G占占用存储空间：用存储空间：n+nn+n2 2；G G占用存储空间只与它的顶点数有关占用存储空间只与它的顶点数有关，与边数无关；适用于边稠密的图；，与边数无关；适用于边稠密的图；typedef str
12、uct ArcCell / 弧的定义弧的定义 VRType 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; / 图的种类标志
13、 MGraph;网络的邻接矩阵网络的邻接矩阵ABDCE15972111320 A 1 41 B 0 4 52 C 3 53 D 2 54 E 0 15 F 1 2 3BACDFE二、图的邻接表二、图的邻接表 存储表示存储表示 同一个顶点发出的边同一个顶点发出的边链接在同一个边链表中链接在同一个边链表中，每一个链结点代表一，每一个链结点代表一条边条边(边结点边结点), 结点中有结点中有另一顶点的下标另一顶点的下标 adjvex 和指针和指针 nextedge。1 4230 1201234 A B C D E有向图的邻接表有向图的邻接表ABECD可见，在有向图的可见，在有向图的邻接表中不易找到邻接
14、表中不易找到指向该顶点的弧。指向该顶点的弧。ABECD有向图的逆邻接表有向图的逆邻接表A B C D E 303420 01234在有向图的邻接表在有向图的邻接表中，对每个顶点，中，对每个顶点，链接的是指向该顶链接的是指向该顶点的弧。点的弧。邻接表表示法特点：邻接表表示法特点：1 1）无向图邻接表边结点数是边数的两倍）无向图邻接表边结点数是边数的两倍. .2 2）顶点）顶点vivi的度：在无向图中等于第的度：在无向图中等于第i i个链表中的个链表中的结点数；在有向图邻接表中结点数；在有向图邻接表中, ,第第i i行的结点数等于行的结点数等于顶点顶点i i的出度，在有向图逆邻接表中的出度，在有向
15、图逆邻接表中, ,第第i i行的结点行的结点数等于顶点数等于顶点i i的入度。的入度。3 3）在邻接表上容易找到任一顶点的第一个邻接点）在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点和下一个邻接点4 4）设存储顶点的一维数组大小为）设存储顶点的一维数组大小为n(n(图的顶点数图的顶点数n),n), G G占用存储空间：占用存储空间：n+en+e；G G占用存储空间与它的顶占用存储空间与它的顶点数和边数有关；适用于边稀疏的图；点数和边数有关；适用于边稀疏的图；typedef struct ArcNode int adjvex; / 该弧所指向的顶点的位置 struct ArcNode *
16、nextarc; / 指向下一条弧的指针 InfoType *info; / 该弧相关信息的指针 ArcNode;adjvex nextarc info弧的结点结构弧的结点结构typedef struct VNode VertexType data; / 顶点信息 ArcNode *firstarc; / 指向第一条依附该顶点的弧 VNode, AdjListMAX_VERTEX_NUM; data firstarc顶点的结点结构顶点的结点结构typedef struct AdjList vertices; int vexnum, arcnum; int kind; / 图的种类标志 ALGr
17、aph;图的结构定义图的结构定义三、有向图的十字链表存储表示三、有向图的十字链表存储表示 弧的结点结构弧的结点结构弧尾顶点位置 弧头顶点位置 弧的相关信息指向下一个有相同弧尾有相同弧尾的结点指向下一个有相同弧头有相同弧头的结点typedef struct ArcBox / 弧弧的结构表示的结构表示 int tailvex, headvex; InfoType *info; struct ArcBox *hlink, *tlink; VexNode;顶点的结点结构顶点的结点结构顶点信息数据 指向该顶点的第一条入弧第一条入弧指向该顶点的第一条出弧第一条出弧typedef struct VexNod
18、e / 顶点的结构表示顶点的结构表示 VertexType data; ArcBox *firstin, *firstout; VexNode;typedef struct VexNode xlistMAX_VERTEX_NUM; / 顶点结点(表头向量) int vexnum, arcnum; /有向图的当前顶点数和弧数 OLGraph;有向图的结构表示有向图的结构表示(十字链表十字链表)ABCDABCD0 10 22 02 33 03 13 20123四、无向图的邻接多重表存储表示typedef struct Ebox VisitIf mark; / 访问标记 int ivex, jvex
19、; /该边依附的两个顶点的位置 struct EBox *ilink, *jlink; InfoType *info; / 该边信息指针 EBox;边的结构表示边的结构表示typedef struct / 邻接多重表邻接多重表 VexBox adjmulistMAX_VERTEX_NUM; int vexnum, edgenum; AMLGraph;顶点的结构表示顶点的结构表示typedef struct VexBox VertexType data; EBox *firstedge; / 指向第一条依附该顶点的边 VexBox;无向图的结构表示无向图的结构表示ABCDE01234ABCDE0
20、103212324417.3 图的遍历图的遍历 从图中某个顶点出发游历图，访遍图中其余顶点，并且使图中的每个顶点仅被访问一次的过程。深度优先搜索深度优先搜索广度优先搜索广度优先搜索遍历应用举例遍历应用举例 从图中某个顶点V0 出发，访问此顶点，然后依次从依次从V0的各个未被访问的邻接的各个未被访问的邻接点出发深度优先搜索遍历图点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。一、深度优先搜索遍历图一、深度优先搜索遍历图连通图的深度优先搜索遍历连通图的深度优先搜索遍历Vw1SG1SG2SG3W1、W2和和W3 均为均为 V 的邻接点，的邻接点，SG1、SG2 和和 SG3
21、分别为含顶点分别为含顶点W1、W2和和W3 的子图。的子图。访问顶点访问顶点 V ：for (W1、W2、W3 ) 若若该邻接点该邻接点W未被访问未被访问， 则则从它出发进行深度优先搜索遍历。从它出发进行深度优先搜索遍历。w2w3w2从上页的图解可见从上页的图解可见:1. 从深度优先搜索遍历连通图的过程类似于树的先根遍历；解决的办法是：为每个顶点设立一个 “访问标志 visitedw”。2. 如何判别V的邻接点是否被访问？acbdegfF F F F F F F T T T T T T Tacb d gfe acbgfed访问标志访问标志: :访问次序访问次序: :例如例如:0 1 2 3 4
22、 5 6 0234516void DFS(Graph G, int v) / 从顶点从顶点v出发，出发，深度优先搜索遍历连通图深度优先搜索遍历连通图 G visitedv = TRUE; VisitFunc(v); for(w=FirstAdjVex(G, v); w!=0; w=NextAdjVex(G,v,w) if (!visitedw) DFS(G, w); / 对v的尚未访问的邻接顶点w / 递归调用DFS / DFS 首先将图中每个顶点的访问标志设为 FALSE, 之后搜索图中每个顶点，如果未被访问，则以该顶点为起始点，进行深度优先搜索遍历，否则继续检查下一顶点。非连通图的深度优先
23、搜索遍历非连通图的深度优先搜索遍历abchdekfgF 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 8021345678void DFSTraverse(Graph G, Status (*Visit)(int v) / 对图对图 G 作深度优先遍历。作深度优先遍历。 VisitFunc = Visit; for (v=0; vG.vexnum; +v) visitedv = FALSE; / 访问标志数组初始化 for (v=0; vw1, V-w
24、2, V-w8 的路径长度为的路径长度为1；V-w7, V-w3, V-w5 的的路径长度为路径长度为2；V-w6, V-w4 的路径长度为的路径长度为3。w1Vw2w7w6w3w8w5w4 从图中的某个顶点从图中的某个顶点V0出发，并在访问此顶点出发，并在访问此顶点之后之后依次访问依次访问V0的所有的所有未被访问未被访问过的邻接点过的邻接点，之后分别从这些邻接点出发依次访问它们的邻之后分别从这些邻接点出发依次访问它们的邻接点，并使接点，并使“先被访问的顶点的邻接点先被访问的顶点的邻接点”先于先于“后被访问的顶点的邻接点后被访问的顶点的邻接点”被访问被访问，直至图，直至图中所有和中所有和V0有
25、路径相通的顶点都被访问到。有路径相通的顶点都被访问到。 若此时图中尚有顶点未被访问，则另选图中若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。程，直至图中所有顶点都被访问到为止。Vw1w8w3w7w6w2w5w4w1Vw2w7w6w3w8w5w4F F F F F F F F FT T T T T T T TT0 1 2 3 4 5 6 7 8VisitedQV访问次序访问次序: :w1w2w8w4w7w3w5w6 void BFSTraverse(Graph G, Status (*Vi
26、sit)(int v) for (v=0; vG.vexnum; +v) visitedv = FALSE; /初始化访问标志 InitQueue(Q); / 置空的辅助队列Q for ( v=0; vG.vexnum; +v ) if ( !visitedv) / v 尚未访问 / BFSTraverse visitedu = TRUE; Visit(u); / 访问uEnQueue(Q, v); / v入队列while (!QueueEmpty(Q) DeQueue(Q, u); / 队头元素出队并置为u for(w=FirstAdjVex(G, u); w!=0; w=NextAdjVe
27、x(G,u,w) if ( ! visitedw) visitedw=TRUE; Visit(w); EnQueue(Q, w); / 访问的顶点w入队列 / if / while 连通分量连通分量 (Connected component) 当无向图为非连通图时当无向图为非连通图时, 从图中某一顶点出发从图中某一顶点出发, 利用深度优先利用深度优先搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点搜索算法或广度优先搜索算法不可能遍历到图中的所有顶点, 只能访问到该顶点所在的最大连通子图只能访问到该顶点所在的最大连通子图(连通分量连通分量)的所有顶点。的所有顶点。图的连通性问题图的连通性问题
28、LEDHGABFICJKM 若从无向图的每一个连通分量中的一个顶点出发进行遍历若从无向图的每一个连通分量中的一个顶点出发进行遍历, 可求得无向图的所有连通分量。可求得无向图的所有连通分量。 求连通分量的算法求连通分量的算法需要对图的每一个顶点进行检测：若已需要对图的每一个顶点进行检测：若已被访问过，则该顶点一定是落在图中已求得的连通分量上；被访问过，则该顶点一定是落在图中已求得的连通分量上；若还未被访问，则从该顶点出发遍历图，可求得图的若还未被访问，则从该顶点出发遍历图，可求得图的另一另一个连通分量个连通分量。 对于非连通的无向图，所有连通分量的生成树组成了非连对于非连通的无向图，所有连通分量
29、的生成树组成了非连通图的生成森林。通图的生成森林。EDHGIKLABFCJMHGIKLABFCJMED非连通无向图非连通无向图DFS 访问序列访问序列:ALMJBFC DE GKHILABFCJMHGIKLABFCJMEDEDHGIKHGIKLABFCJMED7.4 (连通网的连通网的)最小生成树最小生成树 假设要在 n 个城市之间建立通讯联络网，则连通 n 个城市只需要修建 n-1条线路，如何在最节省经费的前如何在最节省经费的前提下建立提下建立这个通讯网通讯网？问题：问题： 构造网的一棵最小生成树，即： 在 e 条带权的边中选取 n-1 条边（不构成回路），使“权值之和权值之和”为最小。算法
30、二：（克鲁斯卡尔算法）算法二：（克鲁斯卡尔算法）该问题等价于：该问题等价于：算法一：（普里姆算法）算法一：（普里姆算法） 假假设设N N=V V,E E)是是连连通通网网，TETE是是N N上上最最小小 生生 成成 树树 边边 的的 集集 合合 。 算算 法法 从从U U u u0 0(u u0 0V V) )，TETE= = 开开始始，重重复复执执行行下下述述操操作作：在在所所有有u uV V，vvV V-U-U的的边边( (u,vu,v)E E中中找找一一条条代代价价最最小小的的边边（ u u0 0，v v0 0）并并入入集集合合TETE, ,同同时时v v0 0并并入入U U，直直至至U
31、=VU=V为为止止。此此时时TETE中中必必有有n n-1-1条条边边，则则T T=(=(V V,TETE)为为N N的的最最小小生成树。生成树。普里姆算法的基本思想普里姆算法的基本思想: 在生成树的构造过程中，图中 n 个顶点分属两个集合：已落在生成树上的顶点集 U 和尚未落在生成树上的顶点集V-U ，则应在所有连通在所有连通U中顶点和中顶点和V-U中中顶点的边中选取权值最小的边顶点的边中选取权值最小的边。 一般情况下所添加的顶点应满足下列条件:abcdegf例如例如: :195141827168213ae12dcbgf7148531621所得生成树权值和= 14+8+3+5+16+21 =
32、 67 设置一个辅助数组，设置一个辅助数组，对每个顶点对每个顶点，记，记录从顶点集录从顶点集U到到VU具有具有代价最小代价最小的的边：边：struct VertexType adjvex; / U集中的顶点 VRType lowcost; / 边的权值 closedgeMAX_VERTEX_NUM; adjvex lowcostabcdegf195141827168213ae12dcb7aaa19141814e12ee8168d3dd7213c5 50123456U:V-U:ab c d e fgfg16210191418190571250373082114128016210271816270
33、a b c d e f gabcdefgvoid MiniSpanTree_P(MGraph G, VertexType u) /用普里姆算法从顶点u出发构造网G的最小生成树 k = LocateVex ( G, u ); for ( j=0; jG.vexnum; +j ) / 辅助数组初始化 if (j!=k) closedgej = u, G.arcskj.adj ; closedgek.lowcost = 0; / 初始，Uu for (i=0; iG.vexnum; +i) 继续向生成树上添加顶点继续向生成树上添加顶点; k = minimum(closedge); / 求出加入生成
34、树的下一个顶点(k) printf(closedgek.adjvex, G.vexsk); / 输出生成树上一条边 closedgek.lowcost = 0; / 第k顶点并入U集 for (j=0; jG.vexnum; +j) /修改其它顶点的最小边 if (G.arcskj.adj closedgej.lowcost) closedgej = G.vexsk, G.arcskj.adj ; 具体做法具体做法: 先构造一个只含 n 个顶点的子图 SG，然后从权值最小的边开始，若它的添加不使不使SG 中产生回路中产生回路，则在 SG 上加上这条边，如此重复，直至加上 n-1 条边为止。考虑
35、问题的出发点考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。克鲁斯卡尔算法的基本思想：克鲁斯卡尔算法的基本思想：abcdegf195141827168213ae12dcbgf7148531621例如例如: :7121819算法描述算法描述:构造非连通图 ST=( V, ); k = i = 0; / k 计选中的边数 while (kn-1) +i; 检查边集 E 中第第 i 条权值最小的边条权值最小的边(u,v); 若若(u,v)加入加入ST后不使后不使ST中产生回路中产生回路， 则则 输出边输出边(u,v); 且且 k+;普里姆算法普里姆算法克
36、鲁斯卡尔算法克鲁斯卡尔算法时间复杂度时间复杂度O(n2)O(eloge)稠密图稠密图稀疏图稀疏图算法名算法名适应范围适应范围比较两种算法7.7 拓扑排序拓扑排序 问题问题: 假设以有向图表示一个工程的施工图或程序的数据流图，则图中不允许出现回路。 检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序拓扑排序。何谓何谓“拓扑排序拓扑排序”？对有向图进行如下操作： 按照有向图给出的次序关系，将图中顶点排成一个线性序列，对于有向图中没有限定次序关系的顶点，则可以人为加上任意的次序关系。例如：对于下列有向图BDAC可求得拓扑有序序列： A B C D 或 A C B D由此所得顶点的线性序列称之
37、为拓扑有序序列BDAC反之，对于下列有向图不能求得它的拓扑有序序列。因为图中存在一个回路 B, C, D如何进行拓扑排序？如何进行拓扑排序？一、从有向图中选取一个没有前驱没有前驱 的顶点，并输出之； 重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。二、从有向图中删去此顶点以及所删去此顶点以及所 有以它为尾的弧有以它为尾的弧；abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念 没有前驱的顶点没有前驱的顶点 入度为零的顶点入度为零的顶点删除顶点及以它为尾的弧删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减1abcghdf
38、e01234567abcdefgh26673464550 0 1 1 2 2 3 1indegree0 1 2 3 4 5 6 7sab输出次序输出次序: :b02hh1a01ccd0d g f e000算法描述算法描述Status Topologicalsort(ALGraph G) FindinDegree(G,indegree); InitStack(s) For(i=0;inextarc) k=p-adjvex; if(!(- -indegreek) push(s,k); if(countg.vexnum) return ERROR; 7.8 关键路径关键路径问题问题: 假设以有向网表
39、示一个施工流图，弧上的权值表示完成该项子工程所需时间。问：哪些子工程项是“关键工程”？即：哪些子工程项将影响整个工程的完成期限的。abcdefghk64521187244例如例如: :“关键活动”指的是：该弧上的权值增加权值增加 将使有向图上的最长路径的长度增加。最长路径的长度增加。整个工程完成的时间为：从有向图的源点源点到汇点汇点的最长路径。源点汇点6174 如何求关键活动？如何求关键活动？“事件事件(顶点顶点)” 的的 最早发生时间最早发生时间 ve(j)ve(j) = 从源点到顶点从源点到顶点j的最长路径长度的最长路径长度；“事件事件(顶点顶点)” 的的 最迟发生时间最迟发生时间 vl(
40、k) vl(k) = 从顶点从顶点k到汇点的最短路径长度到汇点的最短路径长度。 假设第假设第 i 条弧为条弧为 则则 对第对第 i 项活动言项活动言 “活动活动(弧弧)”的的 最早开始时间最早开始时间 e(i) e(i) = ve(j)； “活动活动(弧弧)”的的 最迟开始时间最迟开始时间 l(i) l(i) = vl(k) dut()；活动活动ai的时间余量的时间余量： l(i) - e(i) 若若lklk = = ekek 表示活动表示活动ai是关键活动。是关键活动。jkai 事件发生时间的计算公式：事件发生时间的计算公式： ve(源点源点) = 0； ve(k) = Maxve(j) +
41、 dut() vl(汇点汇点) = ve(汇点汇点)； vl(j) = Minvl(k) dut()abcdefghk645211872440000000006457115 715 14 1818181818181818181816 1486610807拓扑有序序列拓扑有序序列: a - d - f - c - b - e - h - g - k06457715 14 181814161078660000645777 15 14141602366887 10 算法的实现要点算法的实现要点:显然，求ve的顺序应该是按拓扑有序拓扑有序的次序； 而求vl的顺序应该是按拓扑逆序拓扑逆序的次序；因为拓扑
42、逆序序列即为拓扑有序序列的 逆序列逆序列，因此 应该在拓扑排序的过程中， 另设一个“栈栈”记下拓扑有序序列。 Status TopologicalOrder(ALGraph G,Stack &T) FindinDdegree(G,indegree); InitStack(T); count=0; ve0.G.vexnum-1=0; while(!StackEmpty(S) pop(S,j);Push(T,j); +count; for(p=G.verticesj.firstarc; p; p=p-nextarc) k=p-adjvex; if(-indegreek=0) Push(S,k);
43、if(vej+*(p-info)=dut() vek=vej+*(p-info); if(countvextarc) k=p-adjvex; dut=*(p-info); if(vlk-dutvlj) vlj=vlk-dut; for(j=0;jnextarc) k=p-adjvex; dut=*(p-info); ee=vej; el=vlk-dut; tag=(ee=el)? *: printf(j,k,dut,ee,el,tag); 7.6 两点之间的两点之间的 最短路径问题最短路径问题 求从某个源点到其余各点的求从某个源点到其余各点的最短路径最短路径 每一对顶点之间的最短路径每一对顶点
44、之间的最短路径 求求从源点到其余各点的最短路径从源点到其余各点的最短路径的算法的基本思想的算法的基本思想: 依依最短路径的长度最短路径的长度递增的次序求得递增的次序求得各条路径各条路径源点源点v1其中，从源点到从源点到顶点顶点v的最短路径的最短路径是所有最短路径中长度最短者。v2 这条路径这条路径必定是直接从源点到该点必定是直接从源点到该点v1只含只含一条弧一条弧，并且这条弧的，并且这条弧的权值最小。权值最小。 下一条下一条路径长度次短路径长度次短的最短路径的特点：的最短路径的特点：路径长度最短路径长度最短的最短路径的特点：的最短路径的特点： 它只可能有两种情况：或者是它只可能有两种情况：或者
45、是直接从源直接从源点到该点点到该点v2(只含一条弧只含一条弧)； 或者是或者是从源点从源点经过顶点经过顶点v1，再到达该顶点再到达该顶点v2(由两条弧组由两条弧组成成)。其余最短路径的特点：其余最短路径的特点：再下一条再下一条路径长度次短路径长度次短的最短路径的特点的最短路径的特点: 它可能有三种情况：或者是它可能有三种情况：或者是直接从源点到直接从源点到该点该点v3(只含一条弧只含一条弧)； 或者是或者是从源点经过从源点经过顶点顶点v1，再到达该顶点再到达该顶点(由两条弧组成由两条弧组成)；或；或者是从源点经过顶点者是从源点经过顶点v2，再到达该顶点再到达该顶点v3。 它或者是它或者是直接从
46、源点到该点直接从源点到该点(只含一条弧只含一条弧)； 或者是或者是从源点经过已求得最短路径的从源点经过已求得最短路径的顶点顶点，再到达该顶点再到达该顶点。求最短路径的迪杰斯特拉算法：求最短路径的迪杰斯特拉算法：一般情况下，一般情况下，Distk = 或者或者 = + 。 设置辅助数组设置辅助数组Dist，其中每个分量其中每个分量Distk 表示表示当前当前所求得的从源点到其余各顶点所求得的从源点到其余各顶点 k 的最的最短路径。短路径。1）在所有从源点出发的弧中选取一条权）在所有从源点出发的弧中选取一条权值最小的弧，即为第一条最短路径。值最小的弧，即为第一条最短路径。2）修改其它各顶点的）修改
47、其它各顶点的Distk值。值。假设求得最短路径的顶点为假设求得最短路径的顶点为u，若若 Distu+G.arcsukDistk则将则将 Distk 改为改为 Distu+G.arcsuk。V0和k之间存在弧V0和k之间不存在弧其中的最小值即为最短路径的长度。其中的最小值即为最短路径的长度。v0v1v2v3v4v510060105501030201030100D 0 1 2 3 4 5FFFFFFfinal 0 1 2 3 4 501030 100050500102006000 1 2 3 4 5012345P邻邻接接矩矩阵阵T10T6030T509050T6060TVoid ShortestP
48、ath_DIJ(MGraph G,int v0,PathMatrix &P, ShortPathTable &D) 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; Dv0=0; fimalv0=TRUE; for(i=1;iG.vexnum;+i) min= INFINITY; for(w=0;wG.vexnum;+w) if(!finalw) if(Dwmin) v=w;min=Dw; finalv=TRU
49、E; for(w=0;wG.vexnum;+w) if(!finalw&(min+G.arcsvwDw) Dw=min+G.arcsvw; Pw=Pv; Pww=TRUE; 求每一对顶点之间的最短路径弗洛伊德算法的基本思想是： 从 vi 到 vj 的所有可能存在的路径中，选出一条长度最短的路径。若存在，则存在路径vi,vj / 路径中不含其它顶点若,存在，则存在路径vi,v1,vj / 路径中所含顶点序号不大于1若vi,v2, v2,vj存在， 则存在一条路径vi, , v2, vj / 路径中所含顶点序号不大于2 依次类推，则 vi 至 vj 的最短路径应是上述这些路径中，路径长度最小者。ABC642113DD(-1)D(0) D(1) D(2)0120120120120041104110460461602602602502230370370370PP(-1)P(0)P(1)P(2)0120120120120AB ACABACABABCABABC1BABC BABCBABCBACBC2CACACABCACABCACAB041160230A B CABC012
