【文档说明】课件-算法与数据结构教学第9章图C语言描述第2版张.ppt，共(106)页，1.253 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44681.html

以下为本文档部分文字说明：

9图9.1基本概念9.5最短路径9.2图的周游9.6拓扑排序9.3存储表示9.7关键路径9.4最小生成树重点内容概述:图的深度优先搜索与广度优先搜索最小生成树的Prim算法最小生成树的Kruskal算法单源最短路径Dijkst

ra算法所有顶点对之间最短路径的Floyd算法图的应用：拓扑排序和关键路径9.1图的基本概念:图是由顶点的有穷非空集合V和边（顶点的偶对）的集合E组成，记为G=(V，E)。v0v1v2G1v0v3v2v1G2v0v1v2v6v5v4v3G3V(

G1)={v0,v1,v2}E(G1)={<v0,v1>,<v1,v0>,<v1,v2>}V(G2)={v0,v1,v2,v3}E(G2)={(v0,v1),(v0,v2),(v0,v3),(v1,v

2),(v1,v3),(v2,v3)}V(G3)={v0,v1,v2,v3,v4,v5,v6}E(G3)={(v0,v1),(v0,v2),(v1,v3),(v1,v4),(v2,v5),(v2,v6)}有向图和无向图有向图•定义:若图中的每条边都是有方向的•表示:有向图中的边是

由两个顶点组成的有序对，有序对用尖括号表示如<vi,vj>表示一条有向边，vi是边的始点，vj是边的终点。<vi,vj>和<vj,vi>代表两条不同的有向边。无向图•定义:若图中每条边都是无方向的•表示:无向图中的边是由两个顶点组成的无序对，无序对用圆括号表示无向图中(

vi,vj)和(vj,vi)代表同一条边。在本章中，对所讨论的图加了以下两个约束∶其一是不考虑顶点到其自身的边，即若(vi,vj)或<vi,vj>是E(G)中的边，则vi≠vj；其二是图中不允许一条边重复出现，即如果(vi,vj)或<vi,vj>是E(G)中的边

，则是唯一的。图G的顶点数n和边数e满足以下关系∶若G是有向图，则0≤e≤n(n-1)有向完全图：有n(n-1)条边的有向图若G是无向图，则0≤e≤n(n-1)/2。无向完全图：有n(n-1)/2条

边的无向图完全图具有最多的边数。如图G2就是一个具有4个顶点的无向完全图，边数为:4*(4-1)/2=12。相关概念完全图有向完全图关联与邻接若<vi,vj>是一条有向边，则称顶点vi邻接到vj，或顶点vj邻接于vi，边<vi,vj>与顶点vi，vj相关联。若(vi

,vj)是一条无向边，则vi和vj是相邻顶点，(vi,vj)是与顶点vi和vj相关联的边。度：与顶点v相关联的边数称为顶点的度，记为D(v)。如G2中顶点v0的度为3，入度：若G是一个有向图，则以顶点v为

终点的边的数目称为v的入度，记为ID(v)；出度：以v为始点的边的数目称为v的出度，记为OD(v)。有向图中顶点v的度为其入度和出度之和，即D(v)=ID(v)+OD(v)。如图G1中顶点v1的入度为1，出度为2，度

为3度、入度和出度无论是有向图还是无向图，顶点数n，边数e和度数之间满足以下关系∶==n1ii)/2D(ve设有图G=(V，E)和G’=(V’，E’)，如果V’是V的子集，E’是E的子集，则称G’是G的子图。子图G1如下图给出了

有向图G1的若干子图。143212431121243路径与路径长度路径:图G=(V，E)中，若存在顶点序列vi0,vi1,…,vin，使得(vi0,vi1)，(vi1,vi2)，…，(vin-1,vin)都在E中(若是有

向图，则使得<vi0,vi1>，<vi1,vi2>，…，<vin-1,vin>都在E中)，则称从顶点vi0到vin存在一条路径路径长度:路径上的边数。简单路径:若路径上的顶点除vi0和vin可以相同外,其它顶点都不相同.

回路或环:起点和终点相同的简单路径如图G1中顶点序列v0,v1,v0是一长度为2的有向环；G2中顶点序列v0,v1,v2,v3是一条从顶点v0到v3的长度为3的路径，顶点序列v0,v1,v3,v0,v2是一条从顶点v0到v2的长度为4

的路径，但不是简单路径，顶点序列v0,v1,v3,v0是一长度为3的环。v0v0v1v1v2v2v3G1G2根与有根图有向图中，若存在一顶点v，从该顶点有路径可以到图中其它所有顶点，则称此有向图为有根图，v称为图的根。有根图中的根可能是不唯一的连通图与连通分量连通：图G=(V，

E)中，若从vi到vj有一条路径(从vj到vi也一定有一条路径)，则称vi和vj是连通的连通图：若V(G)中任意两个不同的顶点vi和vj都是连通的(即有路径)，则称G为连通图连通分量：无向图G中的最大连通子图称为G的连通分量强

连通图：有向图G=(V，E)中，若V(G)中任意两个不同的顶点vi和vj都存在从vi到vj以及从vj和vi的路径，则称图G是强连通图强连通分量：有向图的最大强连通子图称为图的强连通分量如图G2和G3都是连通图如图G4是非连通图，它的两个连通分量H1和H2H1v

0H2v0v1v2v1v2v3v3G2G3G4v0v0v1v2v1v2v3v4v5v6v3如左图G1是非强连通图它的两个强连通分量如右图所示v0v1v2v0v2v1G1网络与带权图若图的每条边都赋上一个权，则称为带权图带权的连通图称为网络。通常权是具有某种意义的数，下图为一个网络。

v03v181154v4610v22v39.1.2抽象数据类型ADTGraphisoperation创建一个空图GraphcreateGraph()判断图g是否空图，是则返回1，否则返回0intisNul

lGraph(g)找图中的第一个顶点，如果图是空图则返回NULLVertexfirstVertex(g)找图中顶点vi的下一个顶点VertexnextVertex(g,vi)查找图中值为value的顶点Vertexsearc

hVertex(g,value)在图g中增加一个值为value的顶点GraphaddVertex(g,value)在图g中删除一个顶点和与该顶点相关联的所有边GraphdeleteVertex(g,vertex)在图g中删除一条边e（

<vi,vj>或者(vi,vj)）GraphdeleteEdge(g,vi,vj)在图g中增加一条边<vi,vj>或者(vi,vj)GraphaddEdge(g,vi,vj)判断图g中是否存在一条指定边<vi,vj>或者(vi,vj)intfind

Edge(g,vi,vj)找图g中与顶点v相邻的第一个顶点VertexfirstAdjacent(g,v)//v与返回顶点构成的边也称为与v相关联的第一条边。找图g中与vi相邻的，相对相邻顶点vj的，下

一个相邻顶点VertexnextAdjacent(g,vi,vj)//vi与返回值构成的边也称为是vi与vj构成的边的下一条边endADTGraph9.2图的周游图的周游是从图中某个顶点出发，按照某种方式系统地访问图中的所有顶点，使每个顶点仅被访问一次。也

称图的遍历。–连通图或强连通图：则从图中任意一顶点出发都可以访问图中所有顶点。–由于图中每个顶点都可能与图中其它多个顶点邻接并存在回路，为了避免重复访问已访问过的顶点，在图的周游中，通常对已访问的顶点作标记。–图的遍历通常有两种方法：深度优先搜索和广度

优先搜索。它们对有向图和无向图都适用。深度优先周游深度优先周游(Depth_FirstTraversal)的策略又称为深度优先搜索（Depth_firstSearch），具体思想是∶从图的指定顶点v出发，先访问顶点v，并将其标记为已访问过，然后依次从v未被访问过的邻接顶点w出发进行深度优先搜索

，直到图中与v相连通的所有顶点都被访问过。如果图中还有未被访问的顶点，则从另一未被访问过的顶点出发重复上述过程，直到图中所有顶点都被访问过为止。对图进行深度优先周游时，按访问顶点的先后次序所得到的顶点序列，称

为该图的深度优先周游序列，简称DFS。从上述的搜索方法可知，周游过程是一个递归的过程。V7V6V3V2V5V1V8V4例子：v1v2v4v8v5v3v6v7voiddft(Graphg){

Vertexv;for(v=firstVertex(g);v!=NULL;v=nextVertex(g,v))if(v.mark==FALSE)dfs(g,v);}voiddfs(Graphg,Vertexv){Vertexv1;v.mark=TRU

E;for(v1=firstAdjacent(g,v);v1!=NULL;v1=nextAdjacent(g,v,v1))if(v1.mark==FALSE)dfs(g,v1);}广度优先周游广度优先

周游(Breadth_FirstTraversal)的策略又称为广度优先搜索（Breadth_FirstSearch），具体思想是∶从图的指定顶点v出发，先访问顶点v，并将其标记为已访问过，接着依次访问

v的所有相邻结点w1，w2，…，wx，然后，再依次访问与w1，w2，…，wx邻接的所有未被访问过的顶点，以此类推，直到所有已访问顶点的相邻结点都被访问过为止。如果图中还有未被访问过的顶点，则从某个未被访问过的顶点出发进行广度优先搜索，直到所有顶点都被访问过为止。广度优先周游得到的顶点序列称为广度优

先周游序列，简称BFS序列V7V6V3V2V5V1V8V4例子：V1v2v3v4v5v6v7v8算法：voidbft(Graphg){Vertexv;for(v=firstVertex(g);v!=

NULL;v=nextVertex(g,v))if(v.mark==FALSE)bfs(g,v);}voidbfs(Graphg,Vertexv){Vertexv1,v2;Queueq;/*队列元素的类型为Vertex**/q=create

EmptyQueue();enQueue(q,v);v.mark=TRUE;while(!isEmptyQueue(q)){v1=frontQueue(q);deQueue(q);v1.mark=TRUE;v2=firstAdjacent(g,v1);while(v2!=N

ULL){if(v2.mark==FALSE)enQueue(q,v2);v2=nextAdjacent(g,v1,v2);}}}图的结构较复杂，任意两个顶点间都可能存在联系，因而图的存储方法也很多，应根据具体的应用和施加的操作选择

图的存储表示法9.3图的存储邻接矩阵表示法邻接表表示法邻接多重表表示法、图的十字链表等9.3.1邻接矩阵表示法邻接矩阵是表示顶点间相邻关系的矩阵设G=(V，E)为具有n个顶点的图，其邻接矩阵为具有以下性质

的n阶方阵。><><=的边不是图或若的边是图或若GvvvvGvvvvjiAjijijiji,),(,0,),(,1],[typedefcharVexType;typedeffloatAdjType;typedefst

ruct{intn;/*图的顶点个数*/VexType*vexs;/*顶点信息*/AdjType*arcs[];/*边信息*/}GraphMatrix;无向图G5和有向图G6的邻接矩阵分别为A1和A2v0v3v0v1v2v1v2v4v3邻接矩阵如下：

=00110011110111101A=01000000010101010001000102A如果G是带权的图，wij是边(vi,vj)或<vi,vj>的权，则其邻接矩阵的所有对角线的值为0，其他元素定义为∶><

><=的边不是图或若的边是图或若GvvvvGvvvvwjiAjijijijiij,),(,,),(,],[下图带权图的两种邻接矩阵分别为A3和A4=01011100248206511460385303Av03v181154v4

610v22v3特点无向图的邻接矩阵一定是一对称矩阵无向图的邻接矩阵的第i行(或第i列)非零元素(或非∞元素)个数为第i个顶点的度D(vi)。有向图的邻接矩阵的第i行非零元素(或非∞元素)个数为第i个顶点的出度OD(vi)，第i列非零元素

(或非∞元素)个数就是第i个顶点的入度ID(vi)。邻接矩阵表示图，很容易确定图中任意两个顶点之间是否有边相连。邻接矩阵的存储代价需要存储一个包括n结点的顺序表来保存结点的数据或指向结点的数据指针需存

储一个n×n的相邻矩阵来指示结点间的关系有向图：需n×n个单元来存储相邻矩阵无向图：由于相邻矩阵是对称的只需存储相邻矩阵的下三角部分9.3.2邻接表表示法1、顺序存储的顶点表存放顶点本身的数据信息，表中每个表目对应于图的一个顶点，包括两个字段：顶点字段(vertex)存放顶点v

i的信息指针字段(edgelist)存放与vi相关联的边表中的第一个边结点的地址由顺序存储的顶点表,n个链式存储的边表两部分组成vertexedgelist2、n个链式存储的边表，边表中每个边结点包括三个字段∶相邻顶点字段(endvex)存放通过本边与顶点vi相邻接的顶点vj在顶点表中的位

置j权字段(weight)存放边结点所代表的边的权值(可选项)链字段(nextedge)指向边表的下一个边结点endvexnextedgeweight无向图每条边(vi,vj)在两个顶点vi，vj的边表中都占一个结点，因此，每条边在边表中存储两次

。顶点vi的边表中结点个数为顶点vi的度v0v1v2v31000221∧1∧3∧3∧0123v0v3v1v23有向图顶点vi的边表中每个结点对应的是以vi为始点的一条边，因此，将有向图邻接表的边表称为出边表。顶点

vi的边表中结点个数为顶点vi的出度。也可表示为入边表。(a)是保存出边表的情况(b)是保存入边表的情况。v0v1v2v31∧010∧4∧v0v1v2v4∧1023∧2∧4∧1∧v3v43∧3∧(a)(b)v0v3v0v1v2v1v2v4v3邻接表表示法的存储结构定义如下∶structE

dgeNode;typedefstructEdgeNode*PEdgeNode;typedefstructEdgeNode*EdgeList;structEdgeNode{intendvex;/*相邻顶点字段*/AdjTypeweight;/*边的权*/PEdgeNodenexted

ge;/*链字段*/};/*边表*/typedefstruct{VexTypevertex;/*顶点信息*/EdgeListedgelist;/*边表头指针*/}VexNode;/*顶点表*/typedefstruct{VexNode*vexs;intn;/*图的顶点个

数*/}GraphList;若图G是无向图，则图的邻接表表示的空间代价为O(n+2e)；若图G是有向图，则图的邻接表表示的空间代价为O(n+e)9.3.3两种表示的比较空间开销操作的实现邻接矩阵表示很容易判断两个顶点之间是否有边相连。求无向图中顶点的度，两种

表示都容易；求有向图中顶点的度，邻接矩阵容易，求出度，邻接表表示容易。如何选择合适的存储方法?邻接矩阵表示的空间代价只与图的顶点数有关。若图中边的数目小于顶点的数目，则用邻接表表示图比较节省空间，如果e达到n2数量级时，由于邻接表中增加了辅助的链域，采用邻接矩阵表示图更节

省空间，特别对于无权图而言，邻接矩阵的每个元素只要一个位就可以表示。9.4最小生成树基本概念：生成树DFS生成树BFS生成树最小生成树Prim算法Kruskal算法对于连通的无向图或强连通的

有向图，从任一顶点出发周游，或是对于有根的有向图，从图的根顶点出发周游，可以访问到所有的顶点。周游时经过的边加上所有顶点构成了图的一个连通子图，称为图的一棵生成树构造生成树的过程可以按深度优先周游，也可以按广度优先周游，周游中记录访问的所有顶点以及经过的边，得到的是深度优先生成树或广度

优先生成树，简称为DFS生成树或BFS生成树。例子：无向图v0v1v2v3v4v5v6v7v0v0v1v2v1v2v3v4v5v6v3v4v5v6v7v7DFS生成树BFS生成树v0v0v0v1v3v4v

5v1v3v4v5v1v3v4v5v2v6v2v6v2v6有向图DFS生成树BFS生成树对于非连通的无向图和非强连通的有向图,从任一顶点出发无法访问到所有的顶点，只能得到各连通分量的生成树所组成的生成树林图的生成树不唯一，从不同顶点出发，或从同一顶点出发，但周游的路径不一样，则得到

的生成树都不同9.4.1最小生成树及其性质对于网络，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并把权值最小的生成树称为最小生成树(MinimumSpanningTree)应用：城市中利用最小生成树建立通讯网络花费最

小的方案MST性质∶设G=(V，E)是一个网络，U是顶点集合V的一个真子集。如果边(u,v)的顶点u∈U，v∈V-U，且边(u,v)是图G中所有一个端点在U里，另一端点在V-U里的边中权值最小的边，则一定存在G的一棵最小生成树包括此边(u,

v)注：MST性质可以用反证法证明9.4.2最小生成树的构造利用MST性质，一条一条地选择将要加入的边。算法：prim算法kruskal算法prim算法prim算法的基本思想是∶首先从集合V中任取一顶点(例如取顶

点v0)放入集合U中，这时U={v0}，TE=NULL，然后在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找出权值最小的边(u,v)(u∈U，v∈V-U)，将边加入TE，并将顶点v加入集合U。重复上述操作直到U

=V为止。这时TE中有n-1条边，T=(U，TE)就是G的一棵最小生成树例1654326513566425131163141643142116432142516543214253Kruskal算法的基本思想是∶

设G=(V，E)是网络，最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V，φ)，T中每个顶点自成为一个连通分量。将集合E中的边按递增顺序排列，从小到大依次选择顶点分别在两个连通分量中的边加入图T，则原来的两个连通分量由于该边的连接而

成为一个连通分量。依次类推，直到T中所有顶点都在同一个连通分量上为止，该连通分量就是G的一棵最小生成树Kruskal算法例165432651356642516543212345T=(V,φ)While(T中所含边数<n-1){从E中选取当前最短边(u,v)；从E中删去边

(u,v)；if((u,v)加入T中后不产生回路)将边(u,v)加入T中；}算法描述：9.5最短路径基本概念：路径：如果图中从一个顶点可以到达另一个顶点，则这两个顶点间存在一条路径。(从一个顶点到另一个顶点间可能存在多条路径，而每条路径上经过的边数并不一定相同)路径长度：如果图是一个带权图

，则路径长度为路径上各边的权值的总和。最短路径长度：两个顶点间路径长度最短的那条路径称为两个顶点间的最短路径，其路径长度称为最短路径长度。9.5.1Dijkstra算法设图G中有n个顶点，设置一个集合U，存放已求出最短路径的顶点，V-U是尚未确定最短路径的顶点集合。每个顶点对应

一个距离值，集合U中顶点的距离值是从顶点v0到该顶点的最短路径长度，集合V-U中顶点的距离值是从顶点v0到该顶点的只包括集合U中顶点为中间顶点的最短路径长度。初始时，集合U中只有顶点v0，顶点v0对应的距离值为0，集合V-U中顶点vi的距离值为边(v0,vi

)的权值(i=1,2,…,n-1)，如果v0和vi间无边直接相连，则vi的距离值为∞在集合V-U中选择距离值最小的顶点vmin加入集合U对集合V-U中各顶点的距离值进行修正，如果加入顶点vmin为中间顶点后，使v0到vi的距离值比原来的距离值更小，则修改vi的距离值反复操作，直到从

v0出发可以到达的所有顶点都在集合U中为止13<V0,V1>8<V0,V2>30<V0,V4>32<V0,V6>V2:8<V0,V2>13<V0,V1>-------13<V0,V2,V3>30<V0,V4>32<V0,V6>V1:13<V0,V1

>--------------13<V0,V2,V3>30<V0,V4>22<V0,V1,V5>20<V0,V1,V6>V3:13<V0,V2,V3>---------------------19<V0,V2,V3,V4>22<V0,V1,V5>20<V0,V1,V6>V4:19<V0

,V2,V3,V4>终点从V0到各终点的最短路径及其长度V1V2V3V4V5V6Vj--------------------------------21<V0,V2,V3,V4,V5>20<V0,V1,V6>V6:20<V0,V1,V6>5164320856230137173

29Dijkstra算法时间复杂度：算法中的初始化部分的时间复杂度为O(n)，求最短路径部分由一个大循环组成，其中外循环运行n-1次，内循环为两个，均运行n-1次算法的时间复杂度为O(n2)Floyd算法基本思想：设图G=(V，E)，有n个顶点，图采用邻接矩

阵作为存储结构。如果边(vi，vj)∈E，则从顶点vi到顶点vj存在一条长度为arcs[i][j]的路径，该路径并不一定是从顶点vi到顶点vj的最短路径，因为可能存在从vi到vj并且包含其它顶点为中间顶点的路径。因此，应该在所有从vi到vj允许其它顶点为中间顶点的路径中，找出

长度最短的路径9.5.2Floyd算法例ACB264311041160230初始：路径：ABACBABCCA046602370加入V2：路径：ABABCBABCCACAB0411602370加入V1：

路径：ABACBABCCACAB046502370加入V3：路径：ABABCBCABCCACAB时间复杂度：Floyd算法中初始化部分由一个循环组成，其中外循环运行n次，内循环也运行n次，初始化部分的时间复杂度为O(n2)。迭代生成矩阵A和路径next

vex的部分为三个循环的嵌套，其时间复杂度为O(n3)Floyd算法的时间复杂度为O(n3)9.6拓扑排序9.6.1AOV网9.6.2拓扑排序9.6.1AOV网基本概念：AOV网：如果用图中的顶点表示活动，边表示活动间的先后关系，则这样的有向图称为顶点活动网(Ac

tivityOnVertexnetwork，简称AOV网)AOV网中的弧表示活动之间存在的制约关系例子：计算机专业的学生必须完成一系列规定的基础课和专业课才能毕业，这时工程就是完成给定的学习计划，而活动就是学习课程，这些课程的名称与代号如表所示在AOV网中

，用顶点表示课程，有向边表示课程之间的优先关系，如果课程Ci是课程Cj的先修课，则在AOV网中必定存在一条有向边<Ci,Cj>。表中各课程的AOV网如下图所示C0C7C8C6C2C3C5C1C49.6.2拓扑排序对于一个AOV网，其所有顶点可以排成一个线性序列vi1，vi2，…，vin，该

线性序列具有以下性质∶如果在AOV网中，从顶点vi到顶点vj存在一条路径，则在线性序列中，顶点vi一定排在顶点vj之前。具有这种性质的线性序列称为拓扑序列，构造拓扑序列的操作称为拓扑排序例：对下图中的A

OV网进行拓扑排序得到的一个拓扑序列：C0,C1,C2,C4,C3,C5,C7,C8,C6，另外一个拓扑序列C0,C7,C8,C1,C4,C2,C3,C6,C5如果一个学生一学期只能选修一门课，则他必须按照某一个拓扑序列的次序学习，才能保证学习任何一门课时，其先修课程已学过。C0C7C

8C6C2C3C5C1C4注意：1、一个AOV网的拓扑序列不一定是唯一的。2、假设AOV网代表一个工程，如果条件限制只能串行工作，则AOV网某一拓扑序列就是整个工程得以顺利完成的一种可行方案。AOV网中一定不能出现回路(因为出现回路意味着，某些活动的开工是

以自己工作的完成作为先决条件，这种现象称为死锁)如图所示的AOV网，就无法把顶点排成满足拓扑序列条件的线性序列。v0v1v2任何无回路的AOV网，其顶点都可以排成一个拓扑序列，方法如下：1)从AOV网中选择一个入度为0的顶

点将其输出。2)在AOV网中删除此顶点及其所有的出边。3)反复执行以上两步，直到所有顶点都已经输出为止，此时整个拓扑排序完成；或者直到剩下的顶点的入度都不为0为止，此时说明AOV网中存在回路，拓扑排序无法再进行。C1C5C3C6C2C4C1

C5C3C6C2C4C1,C5C3C6C2C4C1,C5C3C6C2C4C1,C5C3C6C2C4C1,C5C3C6C2C4C1,C4,C5C3C6C2C1,C4,C5C3C6C2C1,C4,C5C3C6C2C1,C

4,C5C3C6C2C1,C4,C2,C5C3C6C1,C4,C2,C5C3C6C1,C4,C2,C5C3C6C1,C4,C2,C3,C5C6C1,C4,C2,C3,C5C6C1,C4,C2,C3,C5C6C1,C4,C2,

C3,C5,C6C1,C4,C2,C3,C5,C6C1,C4,C2,C3,C5,C6C1,C4,C2,C3,C5,C6C1,C4,C2,C3,C5,C6拓扑排序算法：设AOV网采用邻接表表示，边表为出边表。算法中定义一个indegree数组，存放各顶点的入度。设置一个链栈存储入度为0的顶点。拓扑

排序前，先得到所有结点的入度，然后将所有入度为0的顶点压栈。从栈顶取出一个顶点将其输出，由它的出边表可以得到以该顶点为起点的出边，将这些边终点的入度减1，即删除这些边。如果某条边终点的入度为0，则将该顶点入栈。反复进行上述操作，直到栈为空，如果这时输出的顶点个数小于n，则说明该AOV网

中存在回路，否则，拓扑排序正常结束。算法结束后，拓扑序列存放在变量ptopo中。具体实现时，链栈可以利用顶点表中值为0的indegree字段实现例子：AOV网的邻接表表示如图所示。按上述算法进行拓扑排序C0C1C22257∧36∧C3C4C5C6∧∧C78∧4∧3∧5∧00221

221C86∧1拓扑序列为∶C1,C4,C0,C7,C8,C2,C3,C6,C5设AOV网有n个顶点，e条边，算法最初首先检查入度为零的顶点，并将这些顶点压栈，花费的时间为O(n)。下面进行拓扑排序时，每个顶点都入栈一次，且每个顶点边表中的边

结点都被检查一遍，运行时间为O(n+e)。因此，拓扑排序算法的时间复杂度为O(n+e)算法复杂度：9.7关键路径9.7.1AOE网9.7.2关键路径AOE网：如果在带权的有向图中，用顶点表示事件，用有向

边表示活动，边上的权值表示活动持续的时间，则此带权的有向图称为AOE网(Activityonedgenetwork)。顶点所表示的事件实际上就是它的入边所表示的活动都已完成，它的出边所表示的活动可以开始这样一种状态。9.7.1AOE网9.7.2关键路径问题提出把工程计划表示

为有向图，用顶点表示事件，弧表示活动；每个事件表示在它之前的活动已完成，在它之后的活动可以开始例设一个工程有11项活动，9个事件事件V1——表示整个工程开始事件V9——表示整个工程结束问题：（1）完成整项工程至少需要多少时

间？（2）哪些活动是影响工程进度的关键？987645321a6=2定义AOE网(ActivityOnEdge)——也叫边表示活动的网。AOE网是一个带权的有向无环图，其中顶点表示事件，弧表示活动，权表示活动持续时间路径长度——路径上各活动持续时间之和关键路径——

路径长度最长的路径叫~Ve(j)——表示事件Vj的最早发生时间Vl(j)——表示事件Vj的最迟发生时间e(i)——表示活动ai的最早开始时间l(i)——表示活动ai的最迟开始时间l(i)-e(i)——表示完成活动ai的时间余量关键活动——关键路径上的活动叫~，即l(i

)=e(i)的活动问题分析如何找e(i)=l(i)的关键活动？设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>)则有：（1）e(i)=Ve(j)（2）l(i)=Vl(k)-dut(<j,k>)jka

i如何求Ve(j)和Vl(j)？(1)从Ve(1)=0开始向前递推为头的弧的集合是所有以其中jTnjTjijidutiVeMaxjVei><><=2,,)},,()({)((2)从Vl(n)=Ve(n)开始向后递推为尾的弧的集合

是所有以其中iSniSjijidutjVlMiniVlj11,,)},,()({)(><><=求关键路径步骤求Ve(i)求Vl(j)求e(i)求l(i)计算l(i)-e(i)987645321a6=2V1V2V3V4V5V6V7V8V9顶点

VeVl0645771614180668710161418a1a2a3a4a5a6a7a8a9a10a11活动ell-e00002266046258377077071031616014140033例：AOE网包括11项活动，9个事件，事件v0表

示整个工程可以开始这样一个状态；事件v4表示活动a3、a4已经完成，活动a6、a7可以开始这个状态，事件v8表示整个工程结束。如果权所表示的时间单位是天，则活动a0需要6天完成，活动a1需要4天完成，等等。整个工程一开始，活动a0、a1、a2就

可以并行进行，而活动a3、a4、a5只有当事件v1、v2、v3分别发生后才能进行，当活动a9、a10完成时，整个工程也就完成v1v6a0a3v4a6a9v8v0a1a4a104v2a7a25a8v7v3a5v5611297424关键路径算法计算ee(j)必

须在顶点vj所有前驱顶点的最早发生时间都已经求出的前提下进行，而计算le(i)必须在顶点vi所有后继顶点的最迟发生时间都已经求出的前提下进行，因此，顶点序列必须是一个拓扑序列算法复杂度：设AOE网有n个顶点，e条边

，在求事件可能的最早发生时间及允许的最迟发生时间，以及活动的最早开始时间和最晚开始时间时，都要对图中所有顶点及每个顶点边表中所有的边结点进行检查，时间花费为O(n+e)。因此，求关键路径算法的时间复杂度为O(n+e)小结图是一种复杂的非线

性结构。本章介绍了图的基本概念，图的相邻矩阵和邻接表两种常用的存储表示方法，讨论了图的周游、最小生成树、最短路径、*拓扑排序及*关键路径等问题，并给出了相应的算法。重点是掌握图的存储表示和各种算法的基本思想。作业：P.317复习题3—9网络课堂：9图上机实验

：7.17.2