数据结构图PPT课件.ppt

《数据结构图PPT课件.ppt》由会员分享，可在线阅读，更多相关《数据结构图PPT课件.ppt（49页珍藏版）》请在三一文库上搜索。

1、数据结构 与 算法第七讲：图开场白10/07/20252内容提要v图的定义v图的存储结构v图的遍历v最小生成树v最短路径v拓扑排序v关键路径10/07/20253图的定义10/07/20254v图(Graph)是由顶点的有穷集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中 G 表示一个图，V 是图 G 中顶点的集合，E 是图 G 中边的集合。123576984图的术语（一）v图按有无方向分为无向图和有向图。无向图由顶点和边构成，有向图由顶点和弧构成。弧有弧头和弧尾之分。v图按照边或弧的多少分稀疏图和稠密图。如果任意两个顶点之间都存在边叫完全图，有向的叫有向完全图。若无重复的边或顶点

2、到自身的边则叫简单图。v图中顶点之间有邻接点、依附的概念。无向图顶点的边数叫做度，有向图顶点分为入度和出度。v图上的边或弧上带权则称为网。10/07/20255ABDCABDCABDC北京北京香港香港上海上海台北台北1463168012008087002160图a图b图c图d图的术语（二）10/07/20256v图中顶点存在路径，两顶点存在路径则说明是连通的，如果路径最终回到起始点则称为回路或环，当中不重复叫简单路径。若任意两顶点都是连通的，则图就是连通图，有向则称强连通图。图中有子图，若子图极大连通则就是连通分量，有向则称强连通分量。ABDCABDC图a图b图c思考1：图b是强连通图吗?图c

3、呢？ADCABDC图fEFABC图dEF图e思考2：图d是图f的连通分量吗？图的术语（三）10/07/20257v无向图中连通且n个顶点n-1条边叫生成树。有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林。ABDC图aFEGHABDC图bFEGHABDC图cFEGHABDC图dGEFABDC图eGEF图f图的抽象数据类型10/07/20258ADT 图（Graph）Data 顶点的有穷集合和边的集合。Operation CreateGraph(&G,V,E)：按照顶点集V和边弧集E的定义构造图G。DestroyGraph(&G)：图G存在则销毁。Locat

4、eVex(G,u)：若图G中存在顶点u，则返回图中的位置。GetVex(G,v)：返回图G中顶点v的值。PutVex(G,v,value)：将图G中顶点v赋值为value。FirstAdjVex(G,&v)：返回顶点v的一个邻接顶点，若顶点在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(&

5、G,v,w)：在图G中删除弧，若G是无向图，还需要删除对称弧 DFSTraverse(G)：对图G进行深度优先遍历。HFSTraverse(G)：对图G进行广度优先遍历。endADT内容提要v图的定义v图的存储结构v图的遍历v最小生成树v最短路径v拓扑排序v关键路径10/07/20259图的存储结构v相较于线性表和树，图的存储结构更加复杂v下面4个图是一样的吗？10/07/202510ABDCFEGHFGEHADBCGFHEADBCFGEHADBCv顺序存储的问题：物理位置无法表示元素间关系。v多重链表的问题：每个顶点的指针域个数难以选择。图的存储结构：邻接矩阵（一）v邻接矩阵：一维数组存顶点

6、信息，二维数组存边信息10/07/202511V1的度为2主对角线V1的出度为2V1的入度为1V0V3V2V1V0V1V2V3V0V1V2V3V0V1V2V3顶点数组边数组无向图V0V3V2V1V0V1V2V3V0V1V2V3V0V1V2V3顶点数组边数组有向图图的存储结构：邻接矩阵（二）10/07/202512V0V4V1V3V2962351V0V1V2V3顶点数组V4V0V1V2V3V4V0V1V2V3V4边数组有向网图/*无向网图的邻接矩阵表示*/1.typedef char VertexType;2.typedef int EdgeType;3.#define MAXVEX 1004.

7、define INFINITY 655355.typedef struct 6.VertexType vexsMAXVEX;7.EdgeType arcMAXVEXMAXVEX;8.int numVertexes,numEdges;9.MGraph;10.void CreateMGraph(MGraph G)11.int i,j,k,w;12.printf(输入顶点数和边数：n);13.scanf(%d,%d,&G.numVertexes,&G.numEdges);14.for(i=0;iG.numVertexes;i+)15.scanf(%c,&G.vexsi);16.for(i=0;iG

8、numVertexes;i+)17.for(j=0;jG.numVertexes;j+)18.G.arcij=INFINITY;19.for(k=0;kG.numEdges;k+)20.printf(输入边(vi,vj)的下标i,j和权w:n);21.scanf(%d,%d,%d,&i,&j,&w);22.G.arcij=w;23.G.arcji=G.arcij;24.25.时间复杂度：O(n+n2+e)思考：邻接矩阵的缺点？图的存储结构：邻接表（一）v邻接表：一维数组存顶点（包括数据和指向第一个邻接点的指针），每个顶点vi的所有邻接点构成一个单链表10/07/202513V0V3V2V1无

9、向图下标0123120V0V1V2V3datafirstedgeadjvexnext3201302V0V3V2V1有向图下标012330V0V1V2V3datafirstedgeadjvexnext201下标012312V0V1V2V3datafirstedgeadjvexnext120思考：如何知道某结点的度？如何判断某条边是否存在？如何求一个顶点的所有邻接点？图的存储结构：邻接表（二）10/07/202514V0V4V1V3V2962351有向网图1.typedef char VertexType;2.typedef int EdgeType;3.typedef struct EdgeNo

10、de4.5.int adjvex;6.EdgeType weight;7.struct EdgeNode*next;8.EdgeNode;9.typedef struct VertexNode10.11.VertexType data;12.EdgeNode*firstedge;13.VertexNode,AdjListMAXVEX;14.typedef struct15.16.AdjList adjList;17.int numVertexes,numEdges;18.GraphAdjList;下标012340V0V1V2V3datafirstedgeadjvexnext0344V46921

11、523weight图的存储结构：邻接表（三）10/07/2025151.void CreateALGraph(GraphAdjList&G)/*建立无向图的邻接表结构*/2.int i,j,k;3.EdgeNode*e;4.printf(输入顶点数和边数:n);5.scanf(%d,%d,&G.numVertexes,&G.numEdges);6.for(i=0;iG.numVertexes;i+)/读入顶点信息，建立顶点表7.scanf(%c,&G.adjListi.data);/输入顶点信息8.G.adjListi.firstedge=NULL;/将边表置为空表9.10.for(k=0;k

12、adjvex=j;/邻接序号为j15.e-next=G.adjListi.firstedge;/将e指针指向当前顶点指向的结点16.G.adjListi.firstedge=e;/将当前顶点的指针指向e17.18.e=(EdgeNode*)malloc(sizeof(EdgeNode);/生成边表结点19.e-adjvex=i;/邻接序号为i20.e-next=G.adjListj.firstedge;/将e指针指向当前顶点指向的结点21.G.adjListj.firstedge=e;/将当前顶点的指针指向e22.23.时间复杂度：O(n+e)图的存储结构：十字链表v十字链表：有向图的优化，把

13、邻接表和逆邻接表结合起来。10/07/202516V0V3V2V1有向图datafirstinfirstoutheadvextailvexheadlinktaillink顶点表结点结构边表结点结构下标012330V0V1V2V3datafirstedgeadjvexnext201创建算法的时间复杂度：O(n+e)注意：虚线箭头其实就是逆邻接表的表示下标012301V0V1V2V3datafirstinheadvextailvex23001221firstoutheadlinktaillinkV0有两个入边，所以在v0的firstin指向v1后，v1的headlink指向v2，v2后再无v0的入

14、边顶点，所以其taillink为空V1有两个出边，所以在v1的firstout指向v0后,taillink指向v2和当前顶点下标相同(4)(5)(2)(3)(1)图的存储结构：邻接多重表v邻接多重表：无向图的优化，原来用两个结点表示的一条边，现在用一个结点表示10/07/202517V0V3V2V1无向图下标0123120V0V1V2V3datafirstedgeadjvexnext3201302ivexilinkjvexjlink边表结点结构下标0123011V0V1V2V3datafirstedgeivexilink2233002jvexjlink(1)(2)(3)(4)(5)(6)(7)

15、8)(9)(10)图的存储结构：边集数组v边集数组：两个一维数组。一个存储顶点的信息；另一个存储边的信息，边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成。10/07/202518V0V4V1V3V2962351V0V1V2V3顶点数组V4有向网图beginendweightedges0046edges1109edges2123edges3235edges4341edges5202边数组typedef struct int begin;int end;int weight;Edge;内容提要v图的定义v图的存储结构v图的遍历v最小生成树v最短路径

16、v拓扑排序v关键路径10/07/202519图的遍历v你经常找不到钥匙吗？v图的遍历q从图中某一顶点出发 访遍图中其余顶点，且使每一个顶点仅被 访问一次v两种方法：o深度优先遍历o广度优先遍历10/07/202520你玩游戏的时候讨厌走迷宫吗？深度优先遍历(Depth First Search)10/07/202521ABFGHEDICABFCIGDIEHGIFHAGBDHDEBCADEFGHIv从图中某个顶点v出发，访问此顶点，然后从v的未访问的邻接点出发，深度优先遍历图，直至图中所有和v有路径相同的顶点都被访问到。对于非连通图，则需要对它的连通分量分别进行深度优先遍历。注意：是否与树的某个

17、次序遍历相似？邻接矩阵结构的深度优先遍历实现10/07/2025221.#define TRUE 12.#define FALSE 03.typedef int Boolean;/*Boolean是布尔类型，其值是TRUE或FALSE*/4.Boolean visitedMAX;/*访问标志的数组*/5./*邻接矩阵的深度优先递归算法*/6.void DFS(MGraph G,int i)7.int j;8.visitedi=TRUE;9.printf(%c,G.vexsi);/*打印顶点，也可以为其他操作*/10.for(j=0;jG.numVertexes;j+)11.if(G.arcij

18、1&!visitedj)12.DFS(G,j);/*对未访问过的邻接顶点递归调用*/13.14./*邻接矩阵的深度优先遍历操作*/15.void DFSTraverse(MGraph G)16.int i;17.for(i=0;iG.numVertexes;i+)18.visitedi=FALSE;/*初始化所有顶点状态，都是未访问过状态*/19.for(i=0;iadjvex)9.DFS(GL,p-adjvex);/*对未访问的邻接顶点递归调用*/10.p=p-next;11.12.13./*邻接表的深度优先遍历操作*/14.void DFSTraverse(GraphAdjList GL

19、)15.int i;16.for(i=0;iGL.numVertexes;i+)17.visitedi=FALSE;/*初始化所有顶点状态，都是未访问过状态*/18.for(i=0;iGL.numVertexes;i+)19.if(!visitedi)/*对未访问过的顶点调用DFS，若是连通图，只会执行一次*/20.DFS(GL,i);21.时间复杂度：O(n+e)广度优先遍历(Breath First Search)10/07/202524ABFGHEDICABFGHEDICFCIGABFCIGEEDHDIGEDHGEDH(1)(2)(3)(4)(5)(6)(7)(8)(9)出队列入队列邻接

20、矩阵结构的广度优先遍历实现10/07/2025251.void BFSTraverse(MGraph G)/*邻接矩阵的广度优先遍历算法*/2.int i,j;Queue Q;3.for(i=0;iG.numVertexes;i+)4.visitedi=FALSE;5.InitQueue(&Q);/*初始化一辅助用的队列*/6.for(i=0;iG.numVertexes;i+)/*对每一个顶点做循环*/7.if(!visistedi)8.visistedi=TRUE;/*若是未访问过就处理*/9.printf(%c,G.vexsi);/*打印顶点，也可为其他操作*/10.Enqueue(&Q

21、i);/*将此顶点入队列*/11.while(!QueueEmpty(Q)12.Dequeue(&Q,&i);/*将队中元素出队列，赋值给i*/13.for(j=0;jG.numVertexes;j+)14.if(G.arcij=1&!visitedj)15.visitedj=TRUE;16.printf(%c,G.vexsj);17.EnQueue(&Q,j);18.19.20.21.22.23.时间复杂度：O(n2)邻接表结构的广度优先遍历实现10/07/2025261.void BFSTraverse(GraphAdjList GL)/*邻接表的广度优先遍历算法*/2.int i;Ed

22、geNode*p;Queue Q;3.for(i=0;iGL.numVertexes;i+)visitedi=FALSE;4.InitQueue(&Q);/*初始化一辅助用的队列*/5.for(i=0;iadjvex)/*若此顶点未被访问*/15.visitedp-adjvex=TRUE;16.printf(%c,GL.adjListp-adjvex.data);17.EnQueue(&Q,p-adjvex);/*将此顶点入队列*/18.19.p=p-next;/*指针指向下一个邻接点*/20.21.22.23.24.时间复杂度：O(n+e)深度优先 vs 广度优先v如果存储结构一样，时间复杂

23、度是一样的v应用场景：深度优先更适合找目标，广度优先更适合在不断扩大遍历范围时找到相对最优解。v方法论：深度优先或广度优先是一种生活态度q博览群书不求甚解，还是专攻一门深入钻研？q走马观花蜻蜓点水，还是寻幽探奇深度体验？q四海之内皆兄弟，还是人生的一知己足矣？10/07/202527内容提要v图的定义v图的存储结构v图的遍历v最小生成树v最短路径v拓扑排序v关键路径10/07/202528最小生成树(Minimum Cost Spanning Tree)v假设你是电信工程师，需要为一个镇子的九个村庄架设通信网络qv0-v8是村庄q连线上的数字表示村与村之间的距离q没有连线的表示不可直达，比如中

24、间有高山或湖泊10/07/202529V0V5V4V7V6V1V2V8V31110181617261924122122816207V0V5V4V7V6V1V2V8V31110181617261924122122816207方案一：公里数=11+26+20+22+18+21+24+19=161V0V5V4V7V6V1V2V8V31110181617261924122122816207方案二：公里数=8+12+10+11+16+19+16+7=99最小生成树：普里姆(Prim)算法过程及演示v假设N=(V,E)是连通网，TE是N上最小生成树中边的集合。算法从U=u0(u0V),TE=开始。重复执行

25、下述操作：在所有uU,vV-U的边(u,v)E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。此时TE中必有n-1条边，则T=(U,TE)为N的最小生成树。v算法演示：qU 包含所有蓝灰色的结点；qV-U 包含所有白色的结点；qE 包含所有蓝灰色的边；qTE 包含所有红色的边。10/07/202530V0V5V4V7V6V1V2V8V31110181617261924122122816207最小生成树：普里姆(Prim)算法代码实现10/07/2025311.void MiniSpanTree_Prim(MGraph G)2.int min,i,j,k;3./保

26、存已访问的距离最近邻接结点的下标4.int adjvexMAXVEX;5./*保存已访问的距离最近的邻接结点之间的权值*/6.int lowcostMAXVEX;7./*lowcost为0表示该下标的顶点已加入生成树,一开始生成树中仅有v0*/8.lowcost0=0;9.adjvex0=0;10.for(i=1;iG.numVertexes;i+)11.12./*将其他结点与v0之间的权值存入lowcost数组*/13.lowcosti=G.arc0j;14.adjvexi=0;15.16.for(i=1;iG.numVertexes;i+)17.18./*依次将其余结点加入最小生成树，具体

27、操作见右边代码*/41.42.20.min=INFINITY;21.j=1;k=0;22.while(jG.numVertexes)23.24.if(lowcostj!=0&lowcostj min)25.26.min=lowcostj;27.k=j;28.29.j+;30.31.printf(%d,%d),adjvexk,k);32.lowcostk=0;33.for(j=1;jG.numVertexes;j+)34.35.if(lowcostj!=0&G.arckjlowcostj)36.37.lowcostj=G.arckj;38.adjvexj=k;39.40.适用于稠密图，时间复杂度

28、O(n2)最小生成树：克鲁斯卡尔(Kruscal)算法过程演示v假设N=(V,E)是连通网，令最小生成树的初始状态只有n个顶点而无边的非连通图T=(V,)，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上（即加上该边不会形成回路），则将此边加入到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有顶点都在同一连通分量上为止。v算法演示：qE 包含所有浅色的边；qT 包含所有红色的边；q黑色的边为舍去的边。10/07/202532V0V5V4V7V6V1V2V8V31110181617261924122122816207最小生成树：克

29、鲁斯卡尔(Kruscal)算法代码实现10/07/2025331.void MiniSpanTree_Kruskal(MGraph G)2.int i,n,m;3.Edge edgesMAXEDGE;4.int parentMAXVEX;5./*此处省略将邻接矩阵G转化为边集数组edges并按权由小到大排序的代码*/6.for(i=0;iG.numVertexes;i+)7.parenti=0;8.for(i=0;i0)19.f=parentf;20.return f;21.beginendweightedges0477edges1288edges20110edges30511edges418

30、12edges53716edges61616edges75617edges81218edges96719edges103420edges113821edges122322edges133624edges144526适用于稀疏图，时间复杂度：O(eloge)00000000001234567878158767内容提要v图的定义v图的存储结构v图的遍历v最小生成树v最短路径v拓扑排序v关键路径10/07/202534最短路径10/07/202535v网图:指两顶点之间经过的边上权值之和最少的路径。v非网图：指两顶点之间经过的边数最少的路径。v源点v终点迪杰斯特拉(Dijkstra)算法v用途：求某

31、个源点到其余各顶点的最短路径v思路：按路径长度递增的次序产生最短路径v算法演示：10/07/202536V1V2V3V4V5V0V6V7V815753173236952741.下一个离v0最近的点是v1，2.下一个离v0最近的点是v2，3.下一个离v0最近的点是v4，4.下一个离v0最近的点是v3，5.下一个离v0最近的点是v5，6.下一个离v0最近的点是v6，7.下一个离v0最近的点是v7，8.下一个离v0最近的点是v8，v14v25v47v410v310v612v716v0前驱点1距离v0v1v2v4v3v6v7v8v0到v8的最短路径是迪杰斯特拉(Dijkstra)算法代码实现10/07

32、/2025371.#define MAXVEX 92.#define INFINITY 655353.typedef int PathMatrixMAXVEX;4.typedef int ShortPathTableMAXVEX;5./*Pv的值为前驱顶点的下标*/6./*Dv表示v0到v的最短路径长度和*/7.void SP_Dijkstra(MGraph G,int v0,PathMatrix&P,ShortPathTable&D)8.9.int v,w,k,min;10.int finalMAXVEX;11.for(v=0;vG.numVertexes;v+)12.finalv=0;13

33、Dv=G.matrixv0v;14.Pv=0;15.16.Dv0=0;17./finalw为1表示已求得v0到w的最短路径18.finalv0=1;19.for(v=1;vG.numVertexes;v+)/*按长度递增的次序，依次求得v0 到某个顶点v的最短路径，如右代码*/38.39.20.min=INFINITY;21.for(w=0;wG.numVertexes;w+)22./*寻找当前离v0最近的顶点*/23.if(!finalw&Dwmin)24.25.k=w;26.min=Dw;27.28.29.finalk=1;30.for(w=0;wG.numVertexes;w+)31.

34、/*如果经过k的路径比当前路径短的话*/32.if(!finalw&min+G.matrixkwD-110+D-102所以D-112=D-110+D-102V0V1V2V0V1V2P-1V0V1V2V0V1V2P0所以P-112=P-110 Dvw=L表示从顶点v到顶点w的最短路径长度是L；Pvw=k表示从相应的从顶点v到顶点w的最短路径从v出发要先经过顶点k。弗洛伊德(Floyd)算法代码实现10/07/202539/*Floyd算法，各参数和D，P数组如前定义*/1.void ShortestPath_Floyd(MGraph G,PathMatrix&P,ShortPathTable&D

35、)2.3.int v,w,k;4.for(v=0;vG.numVertexes;v+)/*初始化 D 与 P*/5.for(w=0;wG.numVertexes;w+)6.Dvw=G.matrixvw;7.Pvw=w;8.9.10.for(k=0;kG.numVertexes;k+)11.for(v=0;vG.numVertexes;v+)12.for(w=0;w Dvk+Dkw)14./*如果经过k顶点的路径比原v与w两点之间的路径更短，更新D与P*/15.Dvw=Dvk+Dkw;16.Pvw=Pvk;17.18.19.20.21.时间复杂度：O(n3)思考：刚才两个算法举例都是无向图，那么

36、对有向图而言，两个算法是否依然有效？内容提要v图的定义v图的存储结构v图的遍历v最小生成树v最短路径v拓扑排序v关键路径10/07/202540拓扑排序v在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网(Activity On Vertex Network)。v设G=(V,E)是一个具有n个顶点的有向图，V中的顶点序列v1,v2,，vn，满足若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在顶点vj之前。则称这样的顶点序列为一个拓扑序列。拓扑排序就是对一个有向图构造拓扑序列的过程。10/07/202541导演确定剧本完

37、善电影制作启动投资确定电影制作完成上映剧本初步完成演职人员确定V0V2V5V6人员到位进驻场地V8前期准备场地确定场景拍摄1场景拍摄2场景拍摄3场景拍摄4后期制作1后期制作2商业宣传V7V3V1V4V15V13V9V10V11V12V14V16拓扑排序算法v基本思路：(1)从AOV网中选择一个入度为0的顶点输出;(2)删去此顶点，并删除以此顶点为尾的弧。继续重复这两个步骤，直到输出全部顶点或者AOV网中不存在入度为0的顶点为止。10/07/2025420下标0V0datafirstarcindegree110V182V290V31312324V473V5121V652V756728V872V9

38、111V10132V11910111V1292V131213adjvexnextarc5442652810V0V1V2V3V6V5V4V7V8V9V10V13V12V11143210V0V1V31110V2201V61v3v1v2v6v0001V4V5vertices拓扑排序算法代码实现10/07/2025431.Status TopologicalSort(ALGraph G)2./有向图G采用邻接表存储结构，顶点表和边表结构如前页所示，G.vernum表示顶点数3./若G无回路，则输出G 的顶点的一个拓扑序列并返回OK，否则ERROR4.FindInDegree(G,indegree);/

39、对各顶点求入度indegree0.G.vernum-15.InitStack(S);/建零入度顶点栈S6.for(i=0;inextarc)15.k=p-adjvex;16.if(!(-indegreek)Push(S,k);/若入度减为0，则入栈17./for18./while19.if(countG.vexnum)20.return ERROR;/该有向图有回路21.else 22.return OK;23.时间复杂度：O(n+e)内容提要v图的定义v图的存储结构v图的遍历v最小生成树v最短路径v拓扑排序v关键路径10/07/202544关键路径v与AOV网对应的是AOE网(Activit

40、y On Edge)即边表示活动的网。AOE网是一个带权的有向无环图，其中，顶点表示事件(Event)，弧表示活动，权表示活动持续的时间。通常，AOE网可用来估算工程的完成时间。vAOE网通常研究的问题是：（1）完成整个工程至少需要多少时间？（2）哪些活动是影响工程进度的关键？路径长度最长的路经叫关键路径（Critical Path）。10/07/202545造外壳开始集中其他零部件造发动机造轮子造底盘组装完成外壳完成开始其他零部件完成发动机完成轮子完成底盘完成部件集中到位完成AOV网AOE网230.5220.50.50.50.50.5关键路径算法v活动ai由弧表示vei表示活动ai的最早开始

41、时间 vli表示活动ai的最迟开始时间。vvej表示事件vj的最早开始时间vvlj表示事件vj的最迟开始时间vei=li的活动ai是关键活动，关键活动构成关键路径。10/07/202546事件vjvejvljv100v234v322v466v567v688V2V1V3V4V5V6a1=3a2=2a3=2a4=3a8=1a7=2a6=3V1V3V4V6a2=2a7=2a5=4a5=4活动aieilia101a200a334a434a522a625a766a867关键路径算法代码实现(Part I)10/07/2025471.Status TopologicalSort(ALGraph G，Sta

42、ck&T)2./有向图G采用邻接表存储结构，顶点表和边表结构如前所示，G.vernum表示顶点数3./求各顶点事件的最早开始时间ve，T为拓扑序列顶点栈，S为零入度顶点栈4./若G无回路，则用T返回G一个拓扑序列，且函数值为OK，否则ERROR5.FindInDegree(G,indegree);/对各顶点求入度indegree0.G.vernum-16.InitStack(S);/建零入度顶点栈S7.InitStask(T);8.for(i=0;inextarc)16.k=p-adjvex;/对j号顶点的每个邻接点入度减117.if(!(-indegreek)Push(S,k);/若入度减为

43、0，则入栈18.if(vej+p-data vek)vek=vej+p-data;19./p-data即dut()20./while21.if(countnextarc)8.9.k=p-adjvex;dut=p-data;10.if(vlk-dut vlj)vlj=vlk-dut;11./for12./while13.for(j=0;jnextarc)16.17.k=p-adjvex;dut=p-data;18.ee=vej;el=vlk-dut;19.tag=(ee=el)?*:;20.printf(j,k,dut,ee,el,tag);/输出关键活动21.22.23.时间复杂度：O(n+e)总结回顾v定义和术语v五种存储结构q邻接矩阵/邻接表/十字链表/邻接多重表/边集数组v两种遍历方式：深度优先 和 广度优先v三种应用q最小生成树o普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法q最短路径o迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法q有向无环图的应用o拓扑排序o关键路径10/07/202549