《数据结构与算法分析第六章图2.pdf》由会员分享，可在线阅读，更多相关《数据结构与算法分析第六章图2.pdf（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、6.4 图的生成树和最小生成树图的生成树和最小生成树三大要素三大要素三大要素三大要素(1)n 个顶点个顶点(2)n 1 条边条边(3)没有回路没有回路生成树生成树 是是无向连通图无向连通图 G的某个连通子图的某个连通子图Example 某无向连通图 某无向连通图G及其生成树及其生成树最小生成树最小生成树生成树代价生成树代价生成树代价生成树代价对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，对图中每条边赋于一个权值（代价），则构成一个网，网的生成树网的生成树网的生成树网的生成树GG=(V.T)=(V.
2、T)的的的的代价代价代价代价是是是是T T中各边的权值之和，中各边的权值之和，中各边的权值之和，中各边的权值之和，最小生成树就是网上所有可能的生成树中，最小生成树就是网上所有可能的生成树中，最小生成树就是网上所有可能的生成树中，最小生成树就是网上所有可能的生成树中，代价最小的一类生成树。代价最小的一类生成树。代价最小的一类生成树。代价最小的一类生成树。最小生成树也不一定唯一。最小生成树也不一定唯一。最小生成树也不一定唯一。最小生成树也不一定唯一。【说明】【说明】1.dfsand bfs 形成不同的生成树形成不同的生成树021302133.生成树是生成树是最小子图最小子图。即：。即：G G 并且
3、并且 V(G)=V(G),G 是连通是连通的的,E(G)是是E(G)的最小集的最小集2.如果在生成树上再增加任一条边，将形成回路如果在生成树上再增加任一条边，将形成回路cycle.普里姆（普里姆（普里姆（普里姆（PrimPrim）最小生成树算法最小生成树算法最小生成树算法最小生成树算法设设设设 N=N=（V V，EE）是一个连通网，是一个连通网，是一个连通网，是一个连通网，V=1V=1，2 2，nn是是是是N N的顶点集合，的顶点集合，的顶点集合，的顶点集合，辅助集合辅助集合辅助集合辅助集合U U，初值为初值为初值为初值为 UoUo，用来存放当前所得到的最小生成树的顶点；用来存放当前所得到的最
4、小生成树的顶点；用来存放当前所得到的最小生成树的顶点；用来存放当前所得到的最小生成树的顶点；辅助集合辅助集合辅助集合辅助集合TETE，初值为初值为初值为初值为，用来存放当前所得到的最小生成树的边。用来存放当前所得到的最小生成树的边。用来存放当前所得到的最小生成树的边。用来存放当前所得到的最小生成树的边。PrimPrim算法步骤算法步骤算法步骤算法步骤1.TE=1.TE=,U=u,U=u0 0 2.2.当当当当U UV V，重复下列步骤：重复下列步骤：重复下列步骤：重复下列步骤：(1)(1)选取（选取（选取（选取（u u0 0,v,v0 0)=mincost(u,v)|)=mincost(u,v
5、)|u uU,vU,vV V-U U，保证不形成回路保证不形成回路保证不形成回路保证不形成回路(2)TE=TE+(2)TE=TE+（u u0 0,v,v0 0),),边（边（边（边（u u0 0,v,v0 0)并入并入并入并入TETE(3)U=U+V(3)U=U+V0 0，顶点顶点顶点顶点V V0 0 并入并入并入并入U U初始化：初始化：5 52 21 13 34 46 66 65 55 56 61 1第第1步：步：6 61 14 4第第2步：步：6 61 14 42 2第第3步：步：5 56 61 14 42 2第第4步：步：23 35 56 61 14 4第第5步：步：特点特点特点特点:
6、以连通为主以连通为主以连通为主以连通为主选代价最小的邻接边选代价最小的邻接边选代价最小的邻接边选代价最小的邻接边 V VClosedgeClosedge1 23 4 5 6UV-UTE1 23 4 5 6UV-UTEVEXLOWCOST06VEXLOWCOST061 15 5112,3,4,5,62,3,4,5,60 05 5 50505 5 5 56 6 6 64 4 41,32,4,5,61,341,32,4,5,61,30 05 5 5025026 6 601,3,62,4,5.(3,6)601,3,62,4,5.(3,6)0 05 5 5005006 6 601,3,6,42,5.(6
7、,4)601,3,6,42,5.(6,4)0000301,3,6,4,25.(3,2)0000301,3,6,4,25.(3,2)0000001,3,6,4,2,5.(2.5)0000001,3,6,4,2,5.(2.5)5 52 21 13 34 46 66 65 55 56 6【例子】【例子】克鲁斯卡尔（克鲁斯卡尔（克鲁斯卡尔（克鲁斯卡尔（KruskalKruskal）最小生成树算法最小生成树算法最小生成树算法最小生成树算法KruskalKruskal 算法是逐步给生成树算法是逐步给生成树算法是逐步给生成树算法是逐步给生成树T T中添加不和中添加不和中添加不和中添加不和T T中的边构成回路
8、中的边构成回路中的边构成回路中的边构成回路的当前最小代价边。的当前最小代价边。的当前最小代价边。特点的当前最小代价边。特点特点特点:以最小代价边主以最小代价边主以最小代价边主以最小代价边主设设设设N=N=（V V，EE）是个连通网是个连通网是个连通网是个连通网,算法步骤为：算法步骤为：算法步骤为：算法步骤为：1.1.置生成树置生成树置生成树置生成树T T的初始状态为的初始状态为的初始状态为的初始状态为T=T=（V V，）2.2.当当当当T T中边数中边数中边数中边数nn-1 1时时时时,重复下列步骤重复下列步骤重复下列步骤重复下列步骤:从从从从E E中选取代价最小的边（中选取代价最小的边（中选
9、取代价最小的边（中选取代价最小的边（v,uv,u）,并删除之并删除之并删除之并删除之;若（若（若（若（v,uv,u）依附的顶点依附的顶点依附的顶点依附的顶点v v和和和和u u落在落在落在落在T T中不同的连同分量上，中不同的连同分量上，中不同的连同分量上，中不同的连同分量上，则将边（则将边（则将边（则将边（v,uv,u）并入到并入到并入到并入到T T的边集中；的边集中；的边集中；的边集中；否则，舍去该边，选择下一条代价最小的边否则，舍去该边，选择下一条代价最小的边否则，舍去该边，选择下一条代价最小的边否则，舍去该边，选择下一条代价最小的边.5 52 21 13 34 46 66 65 55
10、56 65 52 23 34 46 66 65 55 56 61 (1,3)1 (1,3)0 0 步骤步骤步骤步骤(v,u)E (v,u)E T T5 53 34 46 66 65 55 56 6步骤步骤步骤步骤(v,u)E (v,u)E T T3 (2,5)3 (2,5)2 (4,6)2 (4,6)5 54 46 66 65 55 56 65 (1,4)5 (1,4)4 (3,6)4 (3,6)5 56 66 65 55 56 66 66 65 55 56 6步骤步骤步骤步骤(v,u)E (v,u)E T T步骤步骤步骤步骤(v,u)E (v,u)E T T6 (2,3)6 (2,3)6 6
11、6 65 56 6边数边数边数边数=n=n-1=51=5代价代价代价代价=15=156.5 6.5 最短路径（最短路径（最短路径（最短路径（Shortest Paths）在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题在有向图中，寻找从某个源点到其余各个顶点或者每一对顶点之间的最短带权路径的运算，称为最短路径问题1.某个源点到其余各顶点的最短路径算法某个源点到其余各顶点的最短路径算法某个源点到其余各顶点的最短路径算法某个源点到其余各顶点的最短路径算法迪杰特拉（迪杰特拉（迪杰特拉（迪杰特拉（DijkstraDijkstra）算法：算法：算法：算法：
12、v0v1v2v3v4v520 10501515201035303453)v0 v2 v3 v12)v0 v2 v34)v0 v41)v0 v2PathLength10254545?算法思想：按路径长度递增的次序产生到各顶点的最短路径算法思想：按路径长度递增的次序产生到各顶点的最短路径算法思想：按路径长度递增的次序产生到各顶点的最短路径算法思想：按路径长度递增的次序产生到各顶点的最短路径?使用使用使用使用DSDS：利用带权邻接矩阵利用带权邻接矩阵利用带权邻接矩阵利用带权邻接矩阵costcost 表示当前找到的从源点表示当前找到的从源点表示当前找到的从源点表示当前找到的从源点V0V0到每个终点到每
13、个终点到每个终点到每个终点V Vi i的最短路径长度的辅助向量的最短路径长度的辅助向量的最短路径长度的辅助向量的最短路径长度的辅助向量distidisti 存储最短路径的向量存储最短路径的向量存储最短路径的向量存储最短路径的向量pathipathi 表示已找到从表示已找到从表示已找到从表示已找到从V0V0出发的最短路径的终点的集合出发的最短路径的终点的集合出发的最短路径的终点的集合出发的最短路径的终点的集合S S?算法步骤：算法步骤：算法步骤：算法步骤：1.1.用用用用cost cost 初始化初始化初始化初始化distdist；置；置；置；置S=V0S=V0；2.2.选择选择选择选择V Vj
14、 j,使得：使得：使得：使得：distj=Mindisti|Vdistj=Mindisti|Vi iV V-S S V Vj j就是当前求得的从就是当前求得的从就是当前求得的从就是当前求得的从V0V0出发的最出发的最出发的最出发的最短路径的终点，并将短路径的终点，并将短路径的终点，并将短路径的终点，并将V Vj j并入并入并入并入S S；3.3.对对对对V V-S S上的所有顶点上的所有顶点上的所有顶点上的所有顶点V Vk k，修改：修改：修改：修改：distk=Mindistj+costj,k,distkdistk=Mindistj+costj,k,distk4.4.重复重复重复重复2 2，
15、3 3，n n-1 1次。次。次。次。举例说明举例说明举例说明举例说明v0v5v2v4v310100605030v152010cost0 1 2 3 4 5 1055020301001060012345终点终点终点终点从从从从v v0 0到各终点的到各终点的到各终点的到各终点的 dist dist 值和最短路径值和最短路径值和最短路径值和最短路径v1v2v4v3v5vjv5v3v2v410(v0,v2)30(v0,v4)100(v0,v5)60(v0,v2,v3)30(v0,v4)100(v0,v5)50(v0,v4,v3)90(v0,v4,v5)60(v0,v4,v3,v5)时间复杂度O（n
16、2）2.每一对顶点之间的最短路径每一对顶点之间的最短路径每一对顶点之间的最短路径每一对顶点之间的最短路径Method 1 每次以一个顶点为源点，重复调用每次以一个顶点为源点，重复调用每次以一个顶点为源点，重复调用每次以一个顶点为源点，重复调用DijkstraDijkstra算法算法算法算法n n次；次；次；次；Method 2 弗洛伊德算法弗洛伊德算法弗洛伊德算法弗洛伊德算法(FloyedFloyed)弗洛伊德算法思想：以弗洛伊德算法思想：以弗洛伊德算法思想：以弗洛伊德算法思想：以A A(0)(0)i,j=costi,j i,j=costi,j 递推出：递推出：递推出：递推出：其中，其中，其中
17、，其中，A Akki,j i,j 表示从表示从表示从表示从 v vi i到到到到v vj j的中间顶点的序号不大于的中间顶点的序号不大于的中间顶点的序号不大于的中间顶点的序号不大于k k 的最短路径长度。最的最短路径长度。最的最短路径长度。最的最短路径长度。最后得到的后得到的后得到的后得到的Ani,j就是从就是从就是从就是从v vi i到到到到v vj j的最短路径长度的最短路径长度的最短路径长度的最短路径长度。0,min111+=kjkAkiAjiAjiAkkkk（vi vi vjvj)A-1(vi v0(vi v0 vjvj)A0判断（判断（判断（判断（vi v0)(v0 vi v0)(v
18、0 vjvj)是否存在，比较路径长度是否存在，比较路径长度是否存在，比较路径长度是否存在，比较路径长度(vi v0 v1(vi v0 v1 vjvj)A1 (vi(vi vkvk vjvj)Ak （vi vi vnvn-1 1 vjvj)An-1(vi(vi vjvj)的的的的最短路径最短路径最短路径最短路径 A(-1)A(0)A(1)A(2)A(3)0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 1 4 0 1 4 0 1 10 3 0 1 10 3 0 1 9 3 1 0 9 2 0 9 2 0 9 2 12 0 9 2 11 0 8 2 2 3 5
19、 0 8 3 4 0 7 3 4 0 6 3 4 0 6 3 4 0 6 3 6 0 6 0 6 0 9 10 6 0 9 10 6 0 Path(-1)Path(0)Path(1)Path(2)Path(3)0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 3 1 1 0 0 1 1 0 0 1 1 0 0 1 1 2 0 1 1 2 0 3 1 2 2 2 0 2 2 0 0 0 2 0 0 1 2 0 0 1 2 0 0 1 3 0 0 3 0 0 0 3 0 0 0 3 0 2 0
20、 3 0 2 0 3 0 以以以以 PathPath(3)(3)为例，对最短路径的读法加以为例，对最短路径的读法加以为例，对最短路径的读法加以为例，对最短路径的读法加以说明。说明。说明。从说明。从从从A A(3)(3)知，顶点知，顶点知，顶点知，顶点1 1到到到到0 0的最短路径的最短路径的最短路径的最短路径长度为长度为长度为长度为distdist10=11,10=11,其最短路径看其最短路径看其最短路径看其最短路径看 pathpath110 0=2 2，pathpath112 2 =3 3，path path 113 3=1 1,表示顶点表示顶点表示顶点表示顶点0 0 顶点顶点顶点顶点2 2
21、 顶点顶点顶点顶点3 3 顶点顶点顶点顶点1;1;从顶点从顶点从顶点从顶点1 1到顶点到顶点到顶点到顶点0 0最短最短最短最短路径为路径为路径为路径为,for(i=0;iCurrentVtxNum;i+)/输出路径长度及路径for(j=1;jCurrentVtxNum;j+)if(i!=j)coutdistij“:”;int next=pathij;coutj;while(next!=i)cout“”next;next=pathinext;cout“”iendl;时间复杂度O（n3）6.6 有向无环图及其应用6.6.1、有向无环图、有向无环图有向无环图（简称为有向无环图（简称为DAG图）是指无
22、环的有向图，它是一类比有向树更一般的特殊有向图。如图图）是指无环的有向图，它是一类比有向树更一般的特殊有向图。如图DAG图和有向图的例子。图和有向图的例子。（c）有向图（b）DAG图6.6.26.6.2拓扑排序拓扑排序拓扑排序拓扑排序(topological sort)topological sort)拓扑排序是一种对非线性结构的有向图进行线性化的重要手段拓扑排序是一种对非线性结构的有向图进行线性化的重要手段拓扑排序是一种对非线性结构的有向图进行线性化的重要手段拓扑排序是一种对非线性结构的有向图进行线性化的重要手段有向无环图常用于描述任务安排问题有向无环图常用于描述任务安排问题。一般地说，一个
23、较大的工程往往被划分成许多子工程，这些子工程称为活动。一般地说，一个较大的工程往往被划分成许多子工程，这些子工程称为活动(Activity)，这些子工程之间通常受到一定条件的约束，但有些子工程没有先决条件。只有这些子工程都顺利完成后，整个工程才能完成。，这些子工程之间通常受到一定条件的约束，但有些子工程没有先决条件。只有这些子工程都顺利完成后，整个工程才能完成。例如，一件设备的生产过程包含着许多工序；一个教学计划包含许多课程等等。在每个计划包含的许多活动之间，各种计划的执行之间可能存在着先决条件。例如，一件设备的生产过程包含着许多工序；一个教学计划包含许多课程等等。在每个计划包含的许多活动之间
24、，各种计划的执行之间可能存在着先决条件。例如，下图是关于计算机专业教学计划中各课程之间的关系。它对应的例如，下图是关于计算机专业教学计划中各课程之间的关系。它对应的有向无环图有向无环图如图所示如图所示课 程 编 号课 程 名 称先 修 课 程高 等 数 学计 算 机 导 论离 散 数 学数 据 结 构高 级 语 言 程 序 设 计编 译 原 理操 作 系 统计 算 机 组 成 原 理计 算 机 图 形 学汇 编 语 言软 件 工 程C1C2C3C4C6C5C11C10C9C8C7C12算 法 分 析无无C1C3，C4C2C2C5，C6C1，C2，C5C3，C5C5，C7，C10C5C3，C5，
25、C8C C1 1C C5 5C C9 9C C7 7C C4 4C C3 3C C6 6C C1212C C8 8C C1111C C1010C C2 2?AOV Network有向图有向图G中顶点中顶点V(G)代表活动代表活动 activities(e.g.the courses)，边，边 E(G)代表活动的优先关系代表活动的优先关系(e.g.C1C3C1 是是C3的前驱课程的前驱课程).?AOVAOV网可解决如下两个问题：网可解决如下两个问题：网可解决如下两个问题：网可解决如下两个问题：（1 1）判定工程的可行性。显然，有回路，整个工程就无法结）判定工程的可行性。显然，有回路，整个工程就无
26、法结）判定工程的可行性。显然，有回路，整个工程就无法结）判定工程的可行性。显然，有回路，整个工程就无法结束束束束（2 2）确定各项活动在整个工程执行中的先后顺序。）确定各项活动在整个工程执行中的先后顺序。）确定各项活动在整个工程执行中的先后顺序。）确定各项活动在整个工程执行中的先后顺序。称这种先后顺序为称这种先后顺序为称这种先后顺序为称这种先后顺序为拓扑有序序列拓扑有序序列拓扑有序序列拓扑有序序列。这种用顶点表示活动，弧表示活动间先后关系的有向图叫做顶点活动网这种用顶点表示活动，弧表示活动间先后关系的有向图叫做顶点活动网(Activity On Vertex Network)，简称，简称AOV
27、网网。a a1 1a a5 5a a4 4a a6 6a a2 2a a3 3a a8 8a a7 7a a9 9如图有如下拓扑有序序列：如图有如下拓扑有序序列：如图有如下拓扑有序序列：如图有如下拓扑有序序列：a a1 1 a a2 2 a a3 3a a4 4 a a5 5 a a6 6 a a7 7 a a8 8 a a9 9a a2 2 a a6 6 a a1 1 a a3 3 a a4 4 a a5 5 a a7 7 a a9 9 a a8 8算法步骤算法步骤算法步骤算法步骤(1)(1)在在在在AOVAOV网中，选取一个没有前驱的顶点输出；网中，选取一个没有前驱的顶点输出；网中，选取一
28、个没有前驱的顶点输出；网中，选取一个没有前驱的顶点输出；(2)(2)删除该顶点和所有以它为弧尾的弧；删除该顶点和所有以它为弧尾的弧；删除该顶点和所有以它为弧尾的弧；删除该顶点和所有以它为弧尾的弧；(3)(3)重复以上两步，直到重复以上两步，直到重复以上两步，直到重复以上两步，直到 AOVAOV网中全部顶点都已输出（得到拓扑有序序列）网中全部顶点都已输出（得到拓扑有序序列）网中全部顶点都已输出（得到拓扑有序序列）网中全部顶点都已输出（得到拓扑有序序列）或者，图中再无没有前驱的顶点（或者，图中再无没有前驱的顶点（或者，图中再无没有前驱的顶点（或者，图中再无没有前驱的顶点（AOVAOV网中有环）网中
29、有环）网中有环）网中有环）abcghdfeabhcdgfe在算法中需要用定量的描述替代定性的概念在算法中需要用定量的描述替代定性的概念算法步骤算法步骤算法步骤算法步骤(1)(1)在在在在AOVAOV网中，选取一个没有前驱的顶点输出；网中，选取一个没有前驱的顶点输出；网中，选取一个没有前驱的顶点输出；网中，选取一个没有前驱的顶点输出；(2)(2)删除该顶点和所有以它为弧尾的弧；删除该顶点和所有以它为弧尾的弧；删除该顶点和所有以它为弧尾的弧；删除该顶点和所有以它为弧尾的弧；(3)(3)重复以上两步，直到重复以上两步，直到重复以上两步，直到重复以上两步，直到 AOVAOV网中全部顶点都已输出（得到拓
30、扑有序序列）网中全部顶点都已输出（得到拓扑有序序列）网中全部顶点都已输出（得到拓扑有序序列）网中全部顶点都已输出（得到拓扑有序序列）或者，图中再无没有前驱的顶点（或者，图中再无没有前驱的顶点（或者，图中再无没有前驱的顶点（或者，图中再无没有前驱的顶点（AOVAOV网中有环）网中有环）网中有环）网中有环）如何实现算法中的如何实现算法中的如何实现算法中的如何实现算法中的(1)(1)和和和和(2)(2)？对于对于对于对于(1)(1)，没有前驱的顶点即入度为，没有前驱的顶点即入度为，没有前驱的顶点即入度为，没有前驱的顶点即入度为0 0的顶点；的顶点；的顶点；的顶点；对于对于对于对于(2)(2)，删除以
31、它为弧尾的所有弧，即让该顶点的所有直接后继的入度减，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减，删除以它为弧尾的所有弧，即让该顶点的所有直接后继的入度减1 1。由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，由此分析知：拓扑排序算法的实现与顶点的入度有密切关系，因此，在选取存储结构时，应考虑：因此，在选取存储结构时，应考虑：因此，在选取存储结构时，应考虑：因此，在选取存储结构时，应考虑：能容易得到各顶点的入度；
32、能容易得到各顶点的入度；能容易得到各顶点的入度；能容易得到各顶点的入度；有利于寻找任一顶点的所有直接后继。有利于寻找任一顶点的所有直接后继。有利于寻找任一顶点的所有直接后继。有利于寻找任一顶点的所有直接后继。为此，采用邻接表作为为此，采用邻接表作为为此，采用邻接表作为为此，采用邻接表作为AOVAOV网的存储结构，并在头结点中增加网的存储结构，并在头结点中增加网的存储结构，并在头结点中增加网的存储结构，并在头结点中增加一个存放顶点入度的域（一个存放顶点入度的域（一个存放顶点入度的域（一个存放顶点入度的域（countcount）用堆栈暂存所有入度为用堆栈暂存所有入度为用堆栈暂存所有入度为用堆栈暂存
33、所有入度为0 0的点的点的点的点AOVAOV网络及其邻接表表示网络及其邻接表表示网络及其邻接表表示网络及其邻接表表示C0C1C2C3C4C500data count firstdata count first1301031destVtxdestVtx nextnext3 0515 0015 0012345C0C1C2C3C4C5 在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就
34、将供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。它加入栈中。它加入栈中。它加入栈中。使用这种栈的拓扑排序算法可以描述如下：使用这种栈的拓扑排序算法可以描述如下：使用这种栈的拓扑排序算法可以描述如下：使用这种栈的拓扑排序算法可以描述如下：(1)(1)建立入度为零的顶点栈建立入度为零的顶点栈建立入度为零的顶点栈建立入度为零的顶点栈;(2)(2)当入度为零的顶点栈不空时当入度为零的顶点栈不空时当入度为零的顶点栈不空时当入度为零的顶点栈不空时,重复执行重复执行重复执行重复执行
35、 从顶点栈中退出一个顶点从顶点栈中退出一个顶点从顶点栈中退出一个顶点从顶点栈中退出一个顶点,并输出之并输出之并输出之并输出之;从从从从AOVAOV网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边网络中删去这个顶点和它发出的边,边的终顶点入边的终顶点入边的终顶点入边的终顶点入度减一度减一度减一度减一;如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至如果边的终顶点入度减至0,0,则该顶点进入度为零的顶点栈则该顶点进入度为零的顶点栈则该顶点进入度为零的顶点栈则该顶点进入度为零的顶点栈;(3)(3)如果输出顶点个数少于如果输出顶点个数少于如果
36、输出顶点个数少于如果输出顶点个数少于AOVAOV网络的顶点个数网络的顶点个数网络的顶点个数网络的顶点个数,则报告网络中则报告网络中则报告网络中则报告网络中存在有向环。存在有向环。存在有向环。存在有向环。在算法实现时，为了建立入度为零的顶点栈，可以不另外分配在算法实现时，为了建立入度为零的顶点栈，可以不另外分配在算法实现时，为了建立入度为零的顶点栈，可以不另外分配在算法实现时，为了建立入度为零的顶点栈，可以不另外分配存储空间，直接利用入度为零的顶点的存储空间，直接利用入度为零的顶点的存储空间，直接利用入度为零的顶点的存储空间，直接利用入度为零的顶点的countcount 数组元素。我们数组元素。
37、我们数组元素。我们数组元素。我们设立了一个栈顶指针设立了一个栈顶指针设立了一个栈顶指针设立了一个栈顶指针toptop，指示当前栈顶的位置，即某一个入度指示当前栈顶的位置，即某一个入度指示当前栈顶的位置，即某一个入度指示当前栈顶的位置，即某一个入度为零的顶点位置。栈初始化时置为零的顶点位置。栈初始化时置为零的顶点位置。栈初始化时置为零的顶点位置。栈初始化时置top top=-1 1，表示空栈。表示空栈。表示空栈。表示空栈。将顶点将顶点将顶点将顶点 I I 进栈时，执行以下指针的修改：进栈时，执行以下指针的修改：进栈时，执行以下指针的修改：进栈时，执行以下指针的修改：countcount i i=
38、toptop;top=itop=i;/toptop指向新栈顶指向新栈顶指向新栈顶指向新栈顶i i,原栈顶元素放在原栈顶元素放在原栈顶元素放在原栈顶元素放在countcount i i 中中中中 退栈操作可以写成：退栈操作可以写成：退栈操作可以写成：退栈操作可以写成：j j=toptop;toptop=countcount toptop;/位于栈顶的顶点的位置记于位于栈顶的顶点的位置记于位于栈顶的顶点的位置记于位于栈顶的顶点的位置记于 j j,toptop退到次栈顶退到次栈顶退到次栈顶退到次栈顶121302 2 03top=-1countcount i i=toptop;top=itop=i;1
39、213-12 2 03top=21213-12 2 23top=4j j=toptop;toptop=countcount toptop;拓扑排序的算法拓扑排序的算法拓扑排序的算法拓扑排序的算法void Graph:TopoSort()int top=-1;/入度为零的顶点栈初始化入度为零的顶点栈初始化for(int i=0;i CurrentVtxnum;i+)/入度为零顶点进栈入度为零顶点进栈if(counti=0)counti=top;top=i;for(i=0;i CurrentVtxnum;i+)/期望输出期望输出n个顶点个顶点if(top=-1)/中途栈空中途栈空,转出转出cout
40、 “网络中有回路网络中有回路(有向环有向环)endl;return;else /继续拓扑排序继续拓扑排序 int j=top;top=counttop;/退栈退栈cout j endl;/输出输出int V=first.adj（）;/扫描该顶点的出边表扫描该顶点的出边表while(V！=-1)if(-countk=0)/该顶点入度减一该顶点入度减一 countk=top;top=k;/减至零减至零V=nextt.adj（）;分析此拓扑排序算法可知，如果分析此拓扑排序算法可知，如果分析此拓扑排序算法可知，如果分析此拓扑排序算法可知，如果AOVAOV网网网网络有络有络有络有n n 个顶点，个顶点，
41、个顶点，个顶点，e e 条边，在拓扑排序的过条边，在拓扑排序的过条边，在拓扑排序的过条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式程中，搜索入度为零的顶点，建立链式程中，搜索入度为零的顶点，建立链式程中，搜索入度为零的顶点，建立链式栈所需要的时间是栈所需要的时间是栈所需要的时间是栈所需要的时间是O(O(n n)。在正常的情况在正常的情况在正常的情况在正常的情况下，有向图有下，有向图有下，有向图有下，有向图有 n n 个顶点，每个顶点进一个顶点，每个顶点进一个顶点，每个顶点进一个顶点，每个顶点进一次栈，出一次栈，共输出次栈，出一次栈，共输出次栈，出一次栈，共输出次栈，出一次栈，共输出 n
42、 n 次。顶点入次。顶点入次。顶点入次。顶点入度减一的运算共执行了度减一的运算共执行了度减一的运算共执行了度减一的运算共执行了 e e 次。所以总的次。所以总的次。所以总的次。所以总的时间复杂度为时间复杂度为时间复杂度为时间复杂度为O(O(n n+e e)。6.6.3 关键路径关键路径关键路径关键路径拓扑排序是一种对非线性结构的有向图进行线性化的重要手段拓扑排序是一种对非线性结构的有向图进行线性化的重要手段拓扑排序是一种对非线性结构的有向图进行线性化的重要手段拓扑排序是一种对非线性结构的有向图进行线性化的重要手段 AOE(Activity On Edge)Networks?有向图中，顶点表示事
43、件，弧表示活动，弧上的权表示完成该活动所有向图中，顶点表示事件，弧表示活动，弧上的权表示完成该活动所有向图中，顶点表示事件，弧表示活动，弧上的权表示完成该活动所有向图中，顶点表示事件，弧表示活动，弧上的权表示完成该活动所需的时间，则称这类有向图为边表示活动的网（需的时间，则称这类有向图为边表示活动的网（需的时间，则称这类有向图为边表示活动的网（需的时间，则称这类有向图为边表示活动的网（AOEAOE网）网）网）网）?AOEAOE网中仅有一个入度为网中仅有一个入度为网中仅有一个入度为网中仅有一个入度为0 0的事件，称为的事件，称为的事件，称为的事件，称为源点源点源点源点，它表示工程的开始；，它表示
44、工程的开始；，它表示工程的开始；，它表示工程的开始；网中也仅有一个出度为网中也仅有一个出度为网中也仅有一个出度为网中也仅有一个出度为0 0的事件，称为的事件，称为的事件，称为的事件，称为汇点汇点汇点汇点，它表示工程的结束。，它表示工程的结束。，它表示工程的结束。，它表示工程的结束。?每一事件每一事件每一事件每一事件V V表示以它为弧头的所有活动已经完成，同时，也表示以它表示以它为弧头的所有活动已经完成，同时，也表示以它表示以它为弧头的所有活动已经完成，同时，也表示以它表示以它为弧头的所有活动已经完成，同时，也表示以它为弧尾的所有活动可以开始。为弧尾的所有活动可以开始。为弧尾的所有活动可以开始。
45、为弧尾的所有活动可以开始。a1=6a4=1a2=4a5=1有有有有4 4个事件：个事件：个事件：个事件：V V1 1，V V2 2，V V3 3，V V5 5V V1 1为源点，为源点，为源点，为源点，V V5 5为汇点为汇点为汇点为汇点有有有有4 4个活动：个活动：个活动：个活动：a a1 1,a,a2 2,a,a4 4,a,a5 5V V3 3表示：表示：表示：表示：a a2 2已完成，已完成，已完成，已完成，a a5 5可以开始可以开始可以开始可以开始?AOEAOE网可解决如下问题：网可解决如下问题：网可解决如下问题：网可解决如下问题：?估算工程的最短工期（从源点到估算工程的最短工期（从
46、源点到估算工程的最短工期（从源点到估算工程的最短工期（从源点到 汇点至少需要多少时间）汇点至少需要多少时间）汇点至少需要多少时间）汇点至少需要多少时间）?找出哪些活动是影响整个工程进展的关键找出哪些活动是影响整个工程进展的关键找出哪些活动是影响整个工程进展的关键找出哪些活动是影响整个工程进展的关键a1=6a4=1a2=4a5=1有有有有4 4个事件：个事件：个事件：个事件：V V1 1，V V2 2，V V3 3，V V5 5V V1 1为源点，为源点，为源点，为源点，V V5 5为汇点为汇点为汇点为汇点有有有有4 4个活动：个活动：个活动：个活动：a a1 1,a,a2 2,a,a4 4,a
47、,a5 5V V3 3表示：表示：表示：表示：a a2 2已完成，已完成，已完成，已完成，a a5 5可以开始可以开始可以开始可以开始Example 求下面 求下面AOE网的关键路径网的关键路径023456startfinisha1=3a2=2a3=2a4=3a5=4a6=3a8=1a7=2?缩短非关键活动都不能缩短整个工期如缩短非关键活动都不能缩短整个工期如a6缩短为缩短为1，则整个工期仍为，则整个工期仍为8。又如。又如a6推迟推迟3天开始，或拖延天开始，或拖延3天完成（天完成（a6=6）均不影响整个工期）均不影响整个工期?分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时
48、间，常可以缩短整个工期。如分析关键路径的目的是找出影响整个工期的关键活动，缩短关键活动的持续时间，常可以缩短整个工期。如a7缩短为缩短为1，则整个工期为，则整个工期为7。此时，再缩短任一关键活动均不能缩短整个工期。即在有多条关键路径时，缩短那些在所有关键路上的关键活动，才能缩短整个工期。此时，再缩短任一关键活动均不能缩短整个工期。即在有多条关键路径时，缩短那些在所有关键路上的关键活动，才能缩短整个工期?关键路径上的活动都是关键活动关键路径上的活动都是关键活动。?路径长度路径长度路径长度路径长度：路径上各活动持续时间的总和路径上各活动持续时间的总和路径上各活动持续时间的总和路径上各活动持续时间的
49、总和即：路径上所有弧的权值之和即：路径上所有弧的权值之和即：路径上所有弧的权值之和即：路径上所有弧的权值之和）?关键路径关键路径关键路径关键路径：从源点到汇点之间路径长度最长的路径，（从源点到汇点之间路径长度最长的路径，（从源点到汇点之间路径长度最长的路径，（从源点到汇点之间路径长度最长的路径，（不一定唯一不一定唯一不一定唯一不一定唯一）?事件事件事件事件V iV i的最早发生时间的最早发生时间的最早发生时间的最早发生时间ve(ive(i)：从源点到从源点到从源点到从源点到V V i i的最长路径长度的最长路径长度的最长路径长度的最长路径长度?活动活动活动活动aiai的最早开始时间的最早开始时
50、间的最早开始时间的最早开始时间e(i)e(i)：等于该活动的弧尾事件等于该活动的弧尾事件等于该活动的弧尾事件等于该活动的弧尾事件V V j j的最早发生时间的最早发生时间的最早发生时间的最早发生时间即若即若即若即若表示活动表示活动表示活动表示活动a ai i，则有则有则有则有e(i)=e(i)=ve(jve(j)vjvkai?事件事件事件事件vkvk的最迟发生时间的最迟发生时间的最迟发生时间的最迟发生时间vl(kvl(k)：是在不推迟整个工期的前提下，该事件最迟必是在不推迟整个工期的前提下，该事件最迟必是在不推迟整个工期的前提下，该事件最迟必是在不推迟整个工期的前提下，该事件最迟必须发生的时间