数据结构 第七章图

数据结构第七章图第一页，共九十九页，编辑于2023年，星期三2【重点掌握】：图的两种遍历方法：遍历的定义、深度优先搜索遍历和广度优先搜索遍历的算法；应用图的遍历算法判断图的连通性及求图的生成树；

用Prim、Kruskal算法求图的最小生成树；用Dijkstra算法求解单源最短路径问题；用Floyd算法求所有顶点间的最短路径问题；利用AOV网进行拓扑排序；利用AOE网求关键路径问题；【掌

握】：掌握图的定义和术语；图的各种存储结构及其构造算法、在实际问题中的求解效率。第二页，共九十九页，编辑于2023年，星期三37.3图的遍历7.3图的遍历：从图的某顶点出发，访问图中所有顶点，并且每个顶点仅访问一次。

图结构的遍历复杂性：（1）在图结构中，没有一个“自然”的首结点，图中的任意一个顶点都可以作为第一个被访问的结点（2）在非连通图中，从一个顶点出发，只能访问它所在的连通分量上的所有顶点，因此，还需考虑如何选取下一个出发点以访问图中的其余连通分量（3）在图结构中，如果有回路存在，那么一个顶点被访问后，有可能沿回路又回到该顶点，考虑如何避免重复访问（4）在图结构中，一个顶点可以和其他多个顶点邻接，当这样的顶点访问过后，考虑如何选取下一个要访问的顶点的问题第三页，共九十九页，编辑于2023年，星期三4

图的遍历方法有深度优先遍历和广度优先遍历两种。7.3.1

深度优先搜索方法：（1）从图的某一顶点V0出发，访问此顶点；（2）依次从V0的未被访问的邻接点出发，深度优先遍历图，直至图中所有和V0相通的顶点都被访问到。

若此时图中尚有顶点未被访问，则另选图中一个未被访问的顶点作起点，重复上述过程，直至图中所有顶点都被访问到。第四页，共九十九页，编辑于2023年，星期三5

V0

V7

V6

V5

V4

V3

V2

V1若图的存储结构为邻接表，则访问邻接点的顺序不唯一，深度优先序列不是唯一的

V0

V1

V3

V2

V7

V6

V5

V4

V0,V1,V3,V4,V7,V2,V5,V6,※求图G以V0为起点的的深度优先序列（设存储结构为邻接矩阵）第五页，共九十九页，编辑于2023年，星期三6voidDFS(GraphG,intv){/*从第v个顶点出发，递归地深度优先遍历图G*//*v是顶点在一维数组中的位置，假设G是非空图*/visited[v]=1;Visit(v);/*访问第v个顶点*/for(w=FirstAdjVex(G,v);w;w=NextAdjVex(G,v,w))if(!visited[w])DFS(G,w);

/*对v的尚未访问的邻接顶点w递归调用DFS*/}辅助数组：intvisited[Max_Vertex_Num];访问标志数组,全局变量，初始时所有分量全为0，visited[v]=1表示顶点v已被访问.visited01234……00000深度优先遍历算法:7.3图的遍历第六页，共九十九页，编辑于2023年，星期三77.3图的遍历在邻接表存储结构上实现深度优先搜索:voidDFSTraverseAL(ALGraphG)/*深度优先遍历以邻接表存储的图G*/{inti;for(i=0;i<G.vexnum;++i)visited[i]=0;/*标志数组初始化*/for(i=0;i<G.vexnum;++i)if(!visited[i])DFSAL(G,i);/*Vi未访问过，从Vi开始DFS搜索*/}第七页，共九十九页，编辑于2023年，星期三8voidDFSAL(ALGraphG,inti){/*从第v个顶点出发，递归地深度优先遍历图G*//*v是顶点的序号，假设G是用邻接表存储*/

EdgeNode*p;

intw;visited[i]=1;Visit(i);/*访问第v个顶点*/for(p=G.vertices[i].firstarc;p;p=p->nextarc){w=p->adjvex;/*w是v的邻接顶点的序号*/if(!visited[w])DFSAL(G,w);

/*若w尚未访问,递归调用DFS*/}}/*DFSAL*/7.3图的遍历第八页，共九十九页，编辑于2023年，星期三9

在遍历时，对图中每个顶点至多调用一次DFS函数，因为一旦某个顶点被标志成已被访问，就不再从它出发进行搜索。因此，遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。

用邻接矩阵做图的存储结构时，查找各个顶点的邻接点所需的时间为O(n2)，其中n为图中顶点数。当以邻接矩阵做存储结构时，深度优先搜索遍历图的时间复杂度为O(n2+n)。

当以邻接表做图的存储结构时，找邻接点所需时间为O(e)，其中e为无向图中边的数或有向图中弧的数。因此，当以邻接表做存储结构时，深度优先搜索遍历图的时间复杂度为O(n+e)。7.3图的遍历第九页，共九十九页，编辑于2023年，星期三10图中某顶点v出发：1）访问顶点v；2）访问v的所有未被访问的邻接点w1,w2,…wk

；3）依次从这些邻接点出发，访问它们的所有未被访问的邻接点;依此类推，直到图中所有访问过的顶点的邻接点都被访问；7.3.2

广度优先遍历7.3图的遍历第十页，共九十九页，编辑于2023年，星期三11

V0

V7

V6

V5

V4

V3

V2

V1V0,V1,V2,V3,V4,V7,V5,V6

V0

V1

V3

V2

V7

V6

V5

V4若图的存储结构为邻接表，则访问邻接点的顺序不唯一，深度优先序列不是唯一的※求图G以V0为起点的的广度优先序列（设存储结构为邻接矩阵）∵先被访问的顶点，其邻接点也要先被访问∴设一队列保存已访问的顶点第十一页，共九十九页，编辑于2023年，星期三12Q※在邻接表存储结构上的广度优先搜索V0V1V2V3V4V7V5V6V1V2V3V0V4V7V5V6V0V7V6V5V4V3V2V17.3图的遍历7012V0V2V3V1datafirstarc01^^adjvexnext3V430511^274564V5V6V72^62^51^47^6^第十二页，共九十九页，编辑于2023年，星期三13voidBFSTraverse(MGraphG)/*从v出发，广度优先遍历连通图G*//*使用辅助队列Q和访问标志数组visited*/{for(v=0;v<G.vexnum;++i)visited[v]=0;InitQueue(Q,G.vexnum);/*初始化空的辅助队列Q*/for(v=0;v<G.vexnum;++v){if(!visited[v])/*若v尚未访问*/

{visited[v]=1;Visit(v);EnQueue(Q,v); while(!QueueEmpty_Sq(Q)) {DeQueue(Q,u);/*队头元素出队,并赋值给u*/

/*访问u所有未被访问的邻接点*/ for(w=0;w<G.vexnum;w++;) if(G.arcs[u,w].adj&&!visited[w]) {visited[w]=1;Visit(w);EnQueue(Q,w);}}/*while*/

}

}}/*BFSTraverse*/7.3图的遍历第十三页，共九十九页，编辑于2023年，星期三14第七

章

图

7.4

连通网的最小生成树 7.4.1

生成树7.4.2

最小生成树7.4.3

构造最小生成树的Prim算法7.4.4

构造最小生成树的Kruskal算法第十四页，共九十九页，编辑于2023年，星期三157.4.1

生成树※生成树：包含了无向图G所有顶点的极小连通子图。1）“极小”含义：一个有n个顶点的连通图的生成树有n-1条边，删除任何一条边，子图不再连通；在生成树中再加一条边必然形成回路。（生成树包含了图中的所有顶点，但只有足以构成生成树的n-1条边）2）一个图可以有许多棵不同的生成树；3）生成树中任意两个顶点间的路径是唯一的；4）含n个顶点n-1条边的图不一定是生成树。7.4最小的生成树第十五页，共九十九页，编辑于2023年，星期三167.4最小的生成树

生成树的含义：n个顶点的图最多可存在n(n-1)/2条边线路。求生成树是为了在网络中连通n个顶点而选择最少的边(n－1)。

例如：一个通信网络中，节点代表了路由器，为了使各路由器之间是连通的（数据可达），且不形成回路(数据回到发送方)，则需建立该网络的生成树。第十六页，共九十九页，编辑于2023年，星期三17求生成树的方法：利用遍历算法。

从连通图中的任一顶点出发进行遍历时，除出发点外，其余顶点必须通过一条边才能到达，所以遍历过程中经历的边有n-1条，它和n个顶点组成了连通图的一棵生成树。

由深度优先搜索得到的是深度优先生成树；由广度优先搜索得到的是广度优先生成树。第十七页，共九十九页，编辑于2023年，星期三18V0V7V6V5V4V3V2V1深度遍历：V0V1V3V4V7V2V5V6V0V7V6V5V4V3V2V17.4最小的生成树V0V7V6V5V4V3V2V1深度优先搜索生成树第十八页，共九十九页，编辑于2023年，星期三19广度遍历：V0V1V2V3V4V7V5V6V0V7V6V5V4V3V2V1V0V7V6V5V4V3V2V1广度优先搜索生成树7.4最小的生成树V0V7V6V5V4V3V2V1第十九页，共九十九页，编辑于2023年，星期三207.4.2

最小生成树的概念

由生成树的定义可知，无向连通图的生成树不是惟一的。

问题的提出：设要在n个城市间建立通信联络网，顶点—表示城市，权表示城市间建立通信线路所需花费代价。希望找到一棵生成树，它的每条边上的权值之和（即建立该通信网所需花费的总代价）最小——最小代价生成树。7.4最小的生成树第二十页，共九十九页，编辑于2023年，星期三21※最小生成树定义：对于一个网络，它的所有生成树中边权值最小的生成树称为最小生成树。

问题分析：n个城市间建立通信网，如何在可能的线路中选择n-1条，能把所有城市（顶点）均连起来，且总耗费（各边权值之和）最小。即：如何在保证n点连通的前题下最节省经费?第二十一页，共九十九页，编辑于2023年，星期三221.Prim

法基本步骤

设连通网络G={V,E}。集合U存放G的最小生成树中的顶点，集合T存放最小生成树之外的顶点。(1)从G中选择某一顶点u0出发，在与它关联的边中选择一个边权最小的边(u0,v);将顶点v加入最小生成树的顶点集合U，在集合T中删除该顶点；(2)用顶点v到集合T中顶点的边权“更新”原集合U中顶点到集合T中顶点的最小边权；(3)从一个顶点在U中，而另一个顶点在T中的各条边中选择权值最小的边(u,v),把顶点v加入到集合U

中。(4)重复(2)、(3)，直到网络中的所有顶点都加入到生成树顶点集合U中为止。7.4.3

构造最小生成树的Prim算法7.4最小的生成树第二十二页，共九十九页，编辑于2023年，星期三23V3V1V4V6V5V2651U={V1}V3V1V4V6V5V251654V3V4V6V5V21V1U={V1,V3}V3V1V4V6V5V216542V3V1V4V6V5V251654U={V1,V3,V6}7.4最小的生成树V3V1V4V6V5V236521655462.过程演示第二十三页，共九十九页，编辑于2023年，星期三24V3V1V4V6V5V216542U={V1,V3,V6,V4

}V3V1V4V6V5V216542U={V1,V3,V6,V4,V2}V3V1V4V6V5V215423U={V1,V3,V6,V4,V2,V5}7.4最小的生成树V3V1V4V6V5V23652165546Prim算法的时间复杂度为O(n2)第二十四页，共九十九页，编辑于2023年，星期三257.4.3构造最小生成树的Kruskal算法1.基本思想：按网中权值递增的顺序构造最小生成树。

2.基本步骤

1）设连通网G=(V,E)，令最小生成树初始状态是只有n个顶点而无边的非连通图T=(V,)，每个顶点自成一个连通分量；2）在E中选取代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中；否则，舍去此边，选取下一条代价最小的边；3）依此类推，直至T中所有顶点都在同一连通分量上为止。7.4最小的生成树第二十五页，共九十九页，编辑于2023年，星期三26V3V1V4V6V5V2V3V4V6V5V21V1V3V1V4V6V5V212V3V1V4V6V5V2123V3V1V4V6V5V2164237.4最小的生成树V3V1V4V6V5V236521655463.过程演示第二十六页，共九十九页，编辑于2023年，星期三27V3V1V4V6V5V2165423V3V1V4V6V5V236521655467.4最小的生成树Kruskal

算法的时间复杂度为O(ne)。第二十七页，共九十九页，编辑于2023年，星期三28

7.5单源最短路径(ShortestPath)

从一个源点到其他各点的最短路径第二十八页，共九十九页，编辑于2023年，星期三29

交通咨询系统、通讯网、计算机网络中经常要寻找两结点间最短路径。例如：交通咨询系统中：咨询A到B的最短路径；计算机网中如何发送E-mail才最节省费用（使E-mail由A到B沿最短路径传送）。

设用带权的有向图表示一个交通运输网，图中：

顶点——表示城市

边——表示城市间的交通联系

权——表示此线路的长度或沿此线路运输所花的时间或费用等

这类问题归结为从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径——最短路径。路径上的第一个顶点为源点，最后一个顶点为终点。

问题的提出:7.5最短路径第二十九页，共九十九页，编辑于2023年，星期三30※最短路径问题：如果从图中某一顶点(源点)到达另一顶点(终点)的路径可能不止一条，如何找到一条路径使沿此路径上各边上的权值总和达到最小。

第三十页，共九十九页，编辑于2023年，星期三31

从一个源点到其他各点的最短路径1.

问题的提法：给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。7.5最短路径10长度最短路径<V0,V1><V0,V3><V0,V3,V2>

<V0,V3,V4>3050902.迪杰斯特拉算法（Dijkstra）（1）基本思想

为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依此类推，直到从顶点v到其它各顶点的最短路径全部求出为止。第三十一页，共九十九页，编辑于2023年，星期三32依据算法的基本思想把V分成两组：（1）S：已求出最短路径的顶点的集合（2）V-S=T：尚未确定最短路径的顶点集合

将T中顶点按如下规则加入到S中：

（1）按递增的次序产生最短路径：从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度;

（2）待求的最短路径最多以已求出最短路径的顶点为中间点：从V0到某顶点的最短路径中，只将S中的顶点作为中间点第三十二页，共九十九页，编辑于2023年，星期三33（2）Dijkstra算法的基本步骤

设V0是源点，初使时令S={V0},T={其余顶点}，T中顶点对应的距离值若存在，<V0,Vi>边权值为<V0,Vi>弧上的权值；若不存在，<V0,Vi>边权值为。1）从T中选取一个其距离值最小的顶点W，加入S；2）①对T中顶点的距离值进行修改：先求出V0到Vi中间只经S中结点的最短路径；若加进W作中间顶点后从V0到Vi的距离值

比

不加W的路径要短，则修改此距离值；②上述最短路径中长度最小者即为下一条长度最短的路径；③将所求最短路径的终点加入S中；3）重复2）直到S中包含所有顶点，即S=V为止。7.5最短路径第三十三页，共九十九页，编辑于2023年，星期三34

1）图用带权邻接矩阵存储；2）引入一个辅助数组dist。它的每一个分量dist[i]表示当前找到的从源点v0到终点vi

的最短路径的长度

初始状态：若从源点v0到顶点vi有边，则dist[i]为该边上的权值；若从源点v0到顶点vi

没有边，则dist[i]为

。3）数组path[]表示从V0到各终点的最短路径上，此顶点的前一顶点的序号；若从V0到某终点无路径，则用-1

作为该结点前一顶点的序号4)数组s[]标识V0到该结点的最短路径是否求出。0表示没求出，1表示已求出。7.5最短路径(3)算法实现第三十四页，共九十九页，编辑于2023年，星期三357.5最短路径260003013501010122601030135010101439000301350001013010000300160001011010000300-1001000P[4]d[4]S[4]P[3]d[3]S[3]P[2]d[2]S[2]P[1]d[1]S[1]顶点4顶点3顶点2顶点1选取点01234第三十五页，共九十九页，编辑于2023年，星期三36

如何从表中读取源点0到终点的最短路径？

以顶点4为例：(1)V0到顶点4的最短路径为60。

(2)path[4]=2→path[2]=3→path[3]=0；

反过来排列，得到路径0,3,2,4，即V0到顶点V4的最短路径。7.5最短路径2600030135010101226010301350101014390003013500010130100003001600010110100003000001000P[4]d[4]S[4]P[3]d[3]S[3]P[2]d[2]S[2]P[1]d[1]S[1]顶点4顶点3顶点2顶点1选取点第三十六页，共九十九页，编辑于2023年，星期三37※Dijkstra算法的时间复杂度为O(n2)第三十七页，共九十九页，编辑于2023年，星期三38

7.6AOV网与拓扑排序第三十八页，共九十九页，编辑于2023年，星期三397.6.1有向无环图的概念1.

有向无环图（directedacyclinegraph）：没有回路的有向图。◆含有公共子式的表达式

例如：表达式(a+b)*(a+b-e/f)

a

-

+

b*/ef用有向无环图表示的表达式◆流程图：

工程流程、生产过程中工序流程、程序流程、课程的流程。常用的两种有向无环图是：AOV网，AOE网。7.6有向无环图及其应用

-

a

+

b*/ef

a

+

b用二叉树表示的表达式第三十九页，共九十九页，编辑于2023年，星期三407.6.2AOV网与拓扑排序1.AOV网

(ActivityOnVertexnetwork)

用顶点表示活动，边表示活动的顺序关系的有向图称为AOV网。

在AOV网中，若从顶点i到顶点j有一条有向路径。则顶点i是顶点j的前驱，j是i的后继。若<i,j>是网中一条弧，则i是j的直接前驱，j是i的直接后继。

在AOV网中，每一条弧表示了活动之间存在的制约关系。

注：AOV网中不允许有回路，这意味着某项活动以自己为先决条件。

例如：计算机专业的学生必须学习一系列的基本课和专业课。学生应按照怎样的顺序来学习呢？

可以把这个问题看做一个大的工程，其活动就是学习每一门课程。7.6有向无环图及其应用第四十页，共九十九页，编辑于2023年，星期三41C1C2C3C4C5C6C7C8C9C10C11无无C1,C2C3，C9C2C4C5C4C1C4，C9C4,C7课程代号

课程名称

先修课程序设计基础高等数学离散数学数据结构普通物理人工智能计算机原理算法分析高级语言编译系统操作系统C1、C2是独立于其它课程的基础课，而另一些课程必须在学完作为它的基础课后才能开始，即有先行课。先行条件规定了课程之间的优先关系。

计算机专业的课程设置及其关系7.6有向无环图及其应用第四十一页，共九十九页，编辑于2023年，星期三42

顶点表示课程，弧表示前提条件活动。若课程i是课程j的先行课，则必然存在弧<i,j>。由此得到如下AOV网：

在安排学习顺序时，必须保证在学习某门课前，已经学习了其先行课。如何设置这些课程的学习顺序，才能无矛盾、顺利地完成学业？7.6有向无环图及其应用C1程序设计基础C3离散数学C2高等数学C4数据结构C5普通物理C6人工智能C7计算机原理C8算法分析C9高级语言C10编译系统C11操作系统第四十二页，共九十九页，编辑于2023年，星期三432.拓扑排序

拓扑序列：有向图D的一个顶点序列称作一个拓扑序列，对于该序列中任两顶点v、u，若在D中v是u前趋，则在序列中v也是u前趋。

拓扑排序：把AOV网络中各顶点按照它们相互之间的领先关系排列成一个线性序列的过程。

拓扑排序的应用：判断工程流程的是否合理.

如何判断AOV网是否存在有向回路？？利用拓扑排序检测AOV网中是否存在环：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。7.6有向无环图及其应用第四十三页，共九十九页，编辑于2023年，星期三443.拓扑排序算法（1）在AOV网中选一个没有前驱的顶点v并将其输出；（2）从网中删除顶点v和所有以v为尾的弧；

（3）重复(1)、(2)，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。7.6有向无环图及其应用第四十四页，共九十九页，编辑于2023年，星期三45C1C3C2C9C5C10C7C6C8C11C4拓扑序列：C17.6有向无环图及其应用第四十五页，共九十九页，编辑于2023年，星期三46C3C2C9C5C10C7C6C8C11C4拓扑序列：C1，C2拓扑序列：C17.6有向无环图及其应用第四十六页，共九十九页，编辑于2023年，星期三47C3C9C5C10C7C6C8C11C4拓扑序列：C1，C2拓扑序列：C1，C2，C37.6有向无环图及其应用第四十七页，共九十九页，编辑于2023年，星期三48C9C5C10C7C6C8C11C4拓扑序列：C1，C2，C3拓扑序列：C1，C2，C3，C97.6有向无环图及其应用第四十八页，共九十九页，编辑于2023年，星期三49C5C10C7C6C8C11C4拓扑序列：C1，C2，C3，C9拓扑序列：C1，C2，C3，C9，C4C5C10C7C6C8C11拓扑序列：C1，C2，C3，C9，C4，C5C10C7C6C8C11拓扑序列：C1，C2，C3，C9，C4，C5，C7C10C6C8C11拓扑序列：C1，C2，C3，C9，C4，C5，C7，C10，C6，C8，C11

一个AOV网的拓扑序列不是唯一的。如何计算机上实现对有向图的拓扑排序？？7.6有向无环图及其应用第四十九页，共九十九页，编辑于2023年，星期三50拓扑排序算法:（1）在AOV网中选一个没有前驱的顶点v并将其输出；（2）从网中删除顶点v和所有以v为尾的弧；

（3）重复(1)、(2)，直至全部顶点均已输出；或者当图中不存在无前驱的顶点为止。7.6有向无环图及其应用※拓扑排序方法的另一种等价描述：

（1）

选择一入度为0顶点v，输出；

（2）

将v邻接到的顶点的入度减1；

（3）

重复(1)、(2)，直至全部顶点均已输出;或图中没有入度为0的顶点为止。第五十页，共九十九页，编辑于2023年，星期三51拓扑排序的数据结构：

以邻接表存储有向图，并在顶点结点中增加该顶点的入度信息。算法：

1）为方便查找入度为0的元素，将邻接表中所有入度为0的顶点进栈2）栈非空时，输出栈顶元素Vj并退栈；3）在邻接表中查找Vj的直接后继Vk，把Vk的入度减1；若Vk的入度为0则进栈；

重复上述操作直至栈空为止。若栈空时输出的顶点个数不是n，则有向图有环；否则，拓扑排序完毕。第五十一页，共九十九页，编辑于2023年，星期三52例:0123450122inlink4432^^^vexnext3^14^130012345^3210405top7.6有向无环图及其应用第五十二页，共九十九页，编辑于2023年，星期三530122inlink4432^^^vexnext3^14^130012345^输出序列：53210405top7.6有向无环图及其应用第五十三页，共九十九页，编辑于2023年，星期三540122inlink4432^^^vexnext3^14^130012345^输出序列：5p321040top7.6有向无环图及其应用第五十四页，共九十九页，编辑于2023年，星期三550122inlink4432^^^vexnext2^14^130012345^p321040top输出序列：57.6有向无环图及其应用第五十五页，共九十九页，编辑于2023年，星期三560122inlink4432^^^vexnext2^14^130012345^p输出序列：5321040top7.6有向无环图及其应用第五十六页，共九十九页，编辑于2023年，星期三570112inlink4432^^^vexnext2^14^130012345^p321040top输出序列：57.6有向无环图及其应用第五十七页，共九十九页，编辑于2023年，星期三580112inlink4432^^^vexnext2^14^130012345^p=NULL321040top输出序列：57.6有向无环图及其应用第五十八页，共九十九页，编辑于2023年，星期三590112inlink4432^^^vexnext2^14^130012345^输出序列：5032104top7.6有向无环图及其应用第五十九页，共九十九页，编辑于2023年，星期三600112inlink4432^^^vexnext2^14^130012345^p32104top输出序列：

507.6有向无环图及其应用第六十页，共九十九页，编辑于2023年，星期三610102inlink4432^^^vexnext2^14^130012345^p332104top输出序列：

50

7.6有向无环图及其应用第六十一页，共九十九页，编辑于2023年，星期三620102inlink4432^^^vexnext2^14^130012345^p332104top输出序列：

507.6有向无环图及其应用第六十二页，共九十九页，编辑于2023年，星期三630002inlink4432^^^vexnext2^14^130012345^p332104top2输出序列：

507.6有向无环图及其应用第六十三页，共九十九页，编辑于2023年，星期三640002inlink4432^^^vexnext2^14^130012345^p332104top2输出序列：

507.6有向无环图及其应用第六十四页，共九十九页，编辑于2023年，星期三650001inlink4432^^^vexnext2^14^130012345^p332104top2输出序列：

507.6有向无环图及其应用第六十五页，共九十九页，编辑于2023年，星期三660001inlink4432^^^vexnext2^14^130012345^p=NULL332104top2输出序列：

507.6有向无环图及其应用第六十六页，共九十九页，编辑于2023年，星期三670001inlink4432^^^vexnext2^14^130012344^输出序列：

502332104top7.6有向无环图及其应用第六十七页，共九十九页，编辑于2023年，星期三680001inlink4432^^^vexnext2^14^130012345^p332104top输出序列：

5027.6有向无环图及其应用第六十八页，共九十九页，编辑于2023年，星期三690001inlink4432^^^vexnext1^14^130012345^p332104top输出序列：

5027.6有向无环图及其应用第六十九页，共九十九页，编辑于2023年，星期三700001inlink4432^^^vexnext1^14^130012345^p332104top输出序列：

5027.6有向无环图及其应用第七十页，共九十九页，编辑于2023年，星期三710000inlink4432^^^vexnext1^14^130012345^p332104top1输出序列：

5027.6有向无环图及其应用第七十一页，共九十九页，编辑于2023年，星期三720000inlink4432^^^vexnext1^14^130012345^p=NULL332104top1输出序列：

5027.6有向无环图及其应用第七十二页，共九十九页，编辑于2023年，星期三730000inlink4432^^^vexnext1^14^130012345^输出序列：

5021332104top7.6有向无环图及其应用第七十三页，共九十九页，编辑于2023年，星期三740000inlink4432^^^vexnext1^14^130012345^p=NULL332104top输出序列：50217.6有向无环图及其应用第七十四页，共九十九页，编辑于2023年，星期三750000inlink4432^^^vexnext1^14^130012345^32104top输出序列：502137.6有向无环图及其应用第七十五页，共九十九页，编辑于2023年，星期三760000inlink4432^^^vexnext1^14^130012345^p32104top输出序列：502137.6有向无环图及其应用第七十六页，共九十九页，编辑于2023年，星期三770000inlink4432^^^vexnext0^14^130012345^p432104top输出序列：502137.6有向无环图及其应用第七十七页，共九十九页，编辑于2023年，星期三780000inlink4432^^^vexnext0^14^130012345^p=NULL432104top输出序列：502137.6有向无环图及其应用第七十八页，共九十九页，编辑于2023年，星期三790000inlink4432^^^vexnext0^14^130012345^输出序列：502134432104top7.6有向无环图及其应用第七十九页，共九十九页，编辑于2023年，星期三800000inlink4432^^^vexnext0^14^130012345^p=NULL32104top输出序列：5021347.6有向无环图及其应用第八十页，共九十九页，编辑于2023年，星期三81拓扑排序算法分析:建邻接表：T(n)=O(n+e)搜索入度为0的顶点的时间：T(n)=O(n)拓扑排序：T(n)=O(n+e)7.6有向无环图及其应用第八十一页，共九十九页，编辑于2023年，星期三827.7AOE网和关键路径１．AOE网(ActivityOnEdges)

如果在无有向环的带权有向图中,※用有向边表示一个工程中的各项活动(Activity),※用边上的权值表示活动的持续时间(Duration),※用顶点表示事件(Event)，每个事件表示在它之前的活动已完成，在它之后的活动可以开始.

这样的有向图叫做用边表示活动的网络，简称AOE网。AOE网在某些工程估算方面非常有用。※用途1：计算完成整个工程至少需要多少时间(假设网络中没有环)?※用途2：为缩短完成工程所需的时间,应当加快哪些活动?

7.6有向无环图及其应用第八十二页，共九十九页，编辑于2023年，星期三83顶点表示事件边表示活动事件Vj发生表示ak已结束ak

VjVi事件Vi发生表示活动ak可以开始

V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1AOE网事件V1——表示整个工程开始事件V6——表示整个工程结束7.6有向无环图及其应用第八十三页，共九十九页，编辑于2023年，星期三84说明：AOV网和AOE网，用都能表示工程各子工程的流程，一个用顶点表示活动，一个用边表示活动，但AOV网侧重表示活动的前后次序，AOE网除表示活动先后次序，还表示了活动的持续时间等，因此可利用AOE网解决工程所需最短时间及哪些子工程拖延会影响整个工程按时完成等问题。实际应用中采用那一种图，取决于要求解的问题。AOE网具有两个性质:(1)只有在某顶点所代表的事件发生之后，从该顶点出发的弧所代表的活动才能开始;(2)只有在进入一个顶点的各弧所代表的活动都已经结束，该顶点所代表的事件才能发生。

7.6有向无环图及其应用第八十四页，共九十九页，编辑于2023年，星期三852.关键路径(CriticalPath)

在AOE网中,有些活动顺序进行，有些活动并行进行。

整个工程结束的条件：从源点到终点的有向路径可能不止一条，其长度也不尽相同，但只有各条路径上所有活动都完成了，整个工程才算完成。

关键路径：完成整个工程所需的时间取决于从源点到终点的最长路径长度（该路径上所有活动的持续时间之和）。这条路径长度最长的路径就叫做关键路径。

7.6有向无环图及其应用V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1AOE网第八十五页，共九十九页，编辑于2023年，星期三86※关键路径长度是整个工程所需的最短工期,即要缩短整个工期，必须加快关键活动的进度。第八十六页，共九十九页，编辑于2023年，星期三873.关键路径的确定设活动ai用弧<j,k>表示，其持续时间记为：dut(<j,k>)。(1)事件Vk的最早可能开始时间Ve[k]

是从源点V0到顶点Vk的最长路径长度。决定了所有从顶点发出的弧所代表的活动能够开工的最早时间.

根据AOE网的性质，只有进入VK的所有活动<Vj,Vk>（1≤j≤n-1)都结束时,

Vk代表的事件才能发生。计算Vk的的最早可能开始时间方法如下:从Ve[1]=0开始递推，Ve[k]=Max{ve[j]+dut(<j,k>)}VjVkVj1≤j≤n-17.6有向无环图及其应用第八十七页，共九十九页，编辑于2023年，星期三88(2)事件Vk的最迟允许开始时间Vl[k]

是在保证终点Vn-1

在Ve[n-1]

时刻完成的前提下(即不拖延工期)，事件Vk的允许的最迟开始时间。

从Vl[n]=Ve[n]开始递推，Vl[k]=Min{vl[j]–dut(<j,k>)}VjVkVj2≤j≤n

设弧<Vk,Vj>代表从Vk出发的活动，为了不拖延工期，Vk发生的最迟时间必须保证不推迟从事件Vk出发的所有活动<Vk,Vj>的终点Vj(2≤j≤n)的最迟时间．

7.6有向无环图及其应用第八十八页，共九十九页，编辑于2023年，星期三89(3)活动ai的最早可能开始时间e[i]

设活动

ai由弧<Vk,Vj>表示，根据AOE网的性质，只有事件Vk发生了，活动ai才能开始。也就是说，活动ai的最早开始时间等于是vk的最早发生时间。因此