1、第9章 图论算法p介绍几个现实生活中发生的问题，可以转化成图论算法；p解决几个普通的图论问题的算法；p深度优先搜索(depth-first search)技巧；p【例例】图中村与村之间的道路是一个较长远的规划目标。图中村与村之间的道路是一个较长远的规划目标。0 引子引子最小生成树问题最小生成树问题9.5节讨论节讨论问题问题1 公路村村通公路村村通项目要求用最小的投入实现每个村都能够有公路通项目要求用最小的投入实现每个村都能够有公路通达。那么应该选择建设哪些道路可以使这个达。那么应该选择建设哪些道路可以使这个投资最小投资最小呢？（假设每条呢？（假设每条道路的建设成本已知）道路的建设成本已知）【例
2、例】下下图为公路规划抽象及造价预算示例图。图为公路规划抽象及造价预算示例图。0 引子引子问题问题2 在同样的抽象图中，假设把在同样的抽象图中，假设把“造价造价”的含义修改成的含义修改成“距离距离”，那么我们就可以问：那么我们就可以问：要走遍每个村庄，并回到起点，该如何走才能够要走遍每个村庄，并回到起点，该如何走才能够使得总的路程最短？使得总的路程最短？88756655444532745BCDFLHWXYZ巡回售货员问题巡回售货员问题（TSP）P.253讨论讨论 通常：用通常：用|V|表示顶点的数量（表示顶点的数量（|V|1），），用用|E|表示边的数量（表示边的数量（|E|0）。）。例例 上上
3、图给出了一个图的示例，在该图中：图给出了一个图的示例，在该图中：集合集合V ，|V|=；集合集合E|E|=“图图”G可以表示为集合：可以表示为集合：G=（V,E）。每条边是。每条边是一个顶点对一个顶点对（v,w）E，并且并且 v,w V。图图的定义的定义88756655444532745BCDFLHWXYZ1 若干定义若干定义 B，C，D，F，H，L，W，X，Y，Z 10(Z,B)，(Z,W)，(B,W)，(B,L)，(B,D)，(D,L)，(W,X)，(W,L)，(L,H)，(L,F)，(X,H)，(X,Y)，(H,Y)，(H,F)，(H,C)，(F,C)，(Y,C)17。(1)无向图无向图
4、（Undirected Graphs）:边（边（v,w）等同于边（）等同于边（w,v）。用圆括号）。用圆括号“（）（）”表示无向边。表示无向边。(a)无向图G1 1230G1=(V1，E1)，V1=0，1，2，3，E1=（0,1）,（0,2）,（0,3）,（2,3）。1 若干定义若干定义 (b)有向图G2 12304(2)有向图有向图（Directed Graphs）:边边不同于边不同于边。用尖括号用尖括号“”表示有向边；有向边也称表示有向边；有向边也称“弧（弧（Arc）”。G2=(V2，E2)，V2=0，1，2，3，4，E2=,，。1 若干定义若干定义(3)简单图简单图（Simple Gra
5、phs）:没有重边和自回路的图没有重边和自回路的图。1201230(a)重边图 (b)自回路图 本书只讨论简单图本书只讨论简单图。1 若干定义若干定义(5)路径、简单路径、回路、无环图路径、简单路径、回路、无环图(4)邻接点邻接点:如果（如果（v,w）或）或 是图中任意一条边，是图中任意一条边，那么称那么称v和和w互为互为“邻接点（邻接点（Adjacent Vertices）”。图图G中从中从vp 到到 vq 的的路径路径:=vp,vi1,vi2,vin,vq 使得使得(vp,vi1),(vi1,vi2),(vin,vq)或或,都属于都属于E(G)路径长度路径长度:=路径中边的数量路径中边的数
6、量 简单路径简单路径:=vi1,vi2,vin 都是不同顶点都是不同顶点 回路回路:=起点和终点相同（起点和终点相同（vp=vq）的路径）的路径 无环图无环图:=不存在任何回路的图不存在任何回路的图 有向无环图有向无环图:=不存在回路的有向图，也称不存在回路的有向图，也称DAG（Directed Acyclic Graph）1 若干定义若干定义(7)有有向完全图向完全图：在顶点数给定为：在顶点数给定为n的情况下，有向边数达的情况下，有向边数达到最大的到最大的n(n-1)条边。条边。(6)无向完全图无向完全图：在顶点数给定为：在顶点数给定为n的情况下，边数达到最大的情况下，边数达到最大的的n(n
7、-1)/2条边。（因为没有重边和自回路边）条边。（因为没有重边和自回路边）02132)1(2|E|V|nnnCn0213)1(|E|V|2nnPnn(8)顶点的顶点的度度(degree)、入度入度(in-degree)、出度出度(out-degree)：度度(v):=与顶点与顶点v相关的边数相关的边数v入度入度(v)=3;出度出度(v)=1;度度(v)=4 给定给定 n 个顶点和个顶点和 e 条边的图条边的图G,则有则有:)(210iiniivdde度其中1 若干定义若干定义(10)权（权（Cost）、网络（、网络（Network）(9)稠密图、稀疏图稠密图、稀疏图：是否满足：是否满足|E|V
8、|log2|V|，作为稠密图，作为稠密图和稀疏图的分界条件。和稀疏图的分界条件。(12)无向图的顶点无向图的顶点连通、连通图、连通分量连通、连通图、连通分量：(11)图图G的的子图子图 G：V(G)V(G)&E(G)E(G)如果无向图从一个顶点如果无向图从一个顶点vi到另一个顶点到另一个顶点vj(ij)有路径，则称顶点有路径，则称顶点vi和和vj是是“连通连通的（的（Connected）”无向图中无向图中任意两顶点都是连通任意两顶点都是连通的，则称该图是的，则称该图是“连通图连通图（Connected Graph）”。无向图的无向图的极大连通子图极大连通子图称为称为“连通分量连通分量（Conn
9、ected Component）”。连通分量的概念包含以下连通分量的概念包含以下4个要点：个要点：子图、连通、子图、连通、极大顶点数、极大边数极大顶点数、极大边数1 若干定义若干定义(13)有向图的有向图的强连通图、连通分量强连通图、连通分量：有有向图中任意一对顶点向图中任意一对顶点vi 和和vj(ij)均既有从均既有从vi到到vj的路径，也有从的路径，也有从vj到到vi的的路径，则称该有向图是路径，则称该有向图是“强连通图强连通图（Strongly Connected Graph）”。有向图的有向图的极大强连通子图极大强连通子图称为称为“强连通分量强连通分量（Strongly Connect
10、ed Component）”。连通分量的概念也包含前面。连通分量的概念也包含前面4个要点。个要点。(14)树树、生成树、生成树：树是图的特例：无环的无树是图的特例：无环的无向图。向图。所谓连通图所谓连通图G的的“生成树生成树（Spanning Tree）”，是，是G的包含其全部的包含其全部n 个顶点的一个个顶点的一个极小连通子图极小连通子图。它必定包含且仅包含。它必定包含且仅包含G的的n-1条边。条边。生成树有可能生成树有可能不唯一不唯一。当且仅当当且仅当G满足下面满足下面4个条件之一（完全等价）：个条件之一（完全等价）：G有有n-1条边，且没有环；条边，且没有环；G有有n-1条边，且是连通的
11、；条边，且是连通的；G中的每一对顶点有且只有一条路径相连；中的每一对顶点有且只有一条路径相连；G是连通的，但删除任何一条边就会使它不连通。是连通的，但删除任何一条边就会使它不连通。1 若干定义若干定义类型名称：图类型名称：图（Graph）操作集：操作集：对于任意的图对于任意的图G Graph，顶点，顶点v、v1和和v2 ertex，以及任一访问顶点的函数以及任一访问顶点的函数visit()，操作举例：，操作举例：数据对象集：数据对象集：一非空的顶点集合一非空的顶点集合Vertex和一个边集合和一个边集合Edge，每条边用对应的一对顶点表示。每条边用对应的一对顶点表示。Graph Create(
12、)：构造并返回一个空图；：构造并返回一个空图；void Destroy(Graph G)：释放图：释放图G占用的存储空间；占用的存储空间；Graph InsertVertex(Graph G,Vertex v)：返回一个在：返回一个在G中增加了新中增加了新顶点顶点v的图的图 Graph InsertEdge(Graph G,Vertex v1,Vertex v2)：返回一个在：返回一个在G中中增加了新边增加了新边(v1,v2)的图；的图；Graph DeleteVertex(Graph G,Vertex v)：删除：删除G中顶点中顶点v及其相关及其相关边，将结果图返回；边，将结果图返回；Gra
13、ph DFS（Graph G,Vertex v,visit()）：在图：在图G中，从顶点中，从顶点v出发出发进行深度优先遍历；进行深度优先遍历；1 若干定义若干定义邻接矩阵邻接矩阵（Adjacency Matrix）边边的信息：用的信息：用邻接矩阵邻接矩阵A n n 表示为表示为:其他的边或如果 0,),(1A Gvvvvjijiji3V0V3V2V1 图的邻接矩阵表示示例图的邻接矩阵表示示例图的邻接矩阵表示示例图的邻接矩阵表示示例 图的表示图的表示顶点顶点信息：有信息：有n个顶点的图个顶点的图G(V,E)用一维数组用一维数组D n 表示；表示；1.1 图的表示图的表示邻接矩阵邻接矩阵 特点：
14、特点：无向图的邻接矩阵一定是一个无向图的邻接矩阵一定是一个对称矩阵对称矩阵。所需存储元。所需存储元素的个数是素的个数是|V|(|V|-1)/2。对于无向图，邻接矩阵的第对于无向图，邻接矩阵的第i行（或第行（或第i列）列）非非0元素元素（或非（或非元素）的个数正好是第元素）的个数正好是第i个顶点的度个顶点的度Degree(vi)。对于有向图，邻接矩阵的第对于有向图，邻接矩阵的第i行（或第行（或第i列）列）非非0元素元素的的个数正好是第个数正好是第i个顶点的个顶点的出度出度(vi)（或入度（或入度(vi)）。）。存储空间代价为存储空间代价为(|V|2)。要确定图中有多少条边，所。要确定图中有多少条
15、边，所花费的花费的时间代价也是时间代价也是(|V|2)。对稀疏图来说，这样的对稀疏图来说，这样的代价明显是不合理的！代价明显是不合理的！1.1 图的表示图的表示邻接表邻接表(Adjacency List)对于图对于图G中的每个顶点中的每个顶点vi，将所有邻接于，将所有邻接于vi的顶点的顶点vj链成一链成一个单链表，这个单链表就称为顶点个单链表，这个单链表就称为顶点vi的邻接表，再将所有点的邻接表，再将所有点的邻接表表头放到一个数组中，就构成了图的的邻接表表头放到一个数组中，就构成了图的邻接表邻接表。无向图的邻接表表示示例无向图的邻接表表示示例VertexFirstEdge顶点域顶点域 边表头指
16、针边表头指针 AdjV Next邻接点域邻接点域 指针域指针域3V0V3V2V11.1 图的表示图的表示邻接表与逆邻接表邻接表与逆邻接表无向图无向图中有中有n 个顶点和个顶点和e条边，则它的邻接表需条边，则它的邻接表需n个头结点和个头结点和2e个表个表边结点。显然，在边边结点。显然，在边稀疏稀疏(e n(n-1)/2)的情况下，用的情况下，用邻接表表示邻接表表示图比邻接矩阵节省存储空间图比邻接矩阵节省存储空间；无向图的邻接表，顶点无向图的邻接表，顶点vi的度恰为第的度恰为第i个链表中的结点数；而在个链表中的结点数；而在有向有向图中图中，第，第i个链表中的结点个数只是顶点个链表中的结点个数只是顶
17、点vi的出度，为便于确定顶点的出度，为便于确定顶点vi的入度，可以建立一个有向图的的入度，可以建立一个有向图的逆邻接表逆邻接表，即对每个顶点，即对每个顶点vi 建立一个建立一个链接以链接以vi为头的弧的链表。为头的弧的链表。例如：例如：1.1 图的表示图的表示2 拓扑排序拓扑排序例例 获得一个计算机科学学位所需的课程。获得一个计算机科学学位所需的课程。Course numberCourse namePrerequisitesC1Programming INoneC2Discrete MathematicsNoneC3Data StructureC1,C2C4Calculus INoneC5Ca
18、lculus IIC4C6Linear AlgebraC5C7Analysis of AlgorithmsC3,C6C8Assembly LanguageC3C9Operating SystemsC7,C8C10Programming LanguagesC7C11Compiler DesignC10C12Artificial IntelligenceC7C13Computational TheoryC7C14Parallel AlgorithmsC13C15Numerical AnalysisC6怎么把这个表转换成图表示怎么把这个表转换成图表示?2 拓扑排序拓扑排序 AOV 网网:=图图 G
19、中中 V(G)表示活动（如：课程），表示活动（如：课程），E(G)表示优先关表示优先关系系(如如 表示表示 C1 是是 C3 的先修课程的先修课程)。C1C3 i 是是 j 的的 前驱前驱:=从从 i 到到 j 有一条路径有一条路径 i是是 j 的的 直接前驱直接前驱:=E(G)所以所以 j 称为称为 i 的的后继后继(直接后继直接后继)偏序偏序:=一种优先关系，同时具有一种优先关系，同时具有传递性传递性(i k,k j i j)和和 非自反性非自反性(i i 是不可能的是不可能的).Note:如果优先关系是自反的，那么必定有一个如果优先关系是自反的，那么必定有一个 i 存在，使得存在，使得
20、i 是是 i 的前驱。那就是说，的前驱。那就是说，i 必须在必须在 i 开始之前被完成（显然开始之前被完成（显然不合理）。因此如果一个项目是不合理）。因此如果一个项目是可行的，可行的，它必然是它必然是非自反非自反的。的。2 拓扑排序拓扑排序【定义定义】拓扑排序拓扑排序是图中顶点的一个线性排序，它使得对任意两个顶点是图中顶点的一个线性排序，它使得对任意两个顶点 i,j,如果如果 i 是是 j 的一个前驱，那么在排序中的一个前驱，那么在排序中 i 出现在出现在 j 的前面。的前面。例例 一个可能的计算机科学学位课程学习表顺序如下：一个可能的计算机科学学位课程学习表顺序如下：Course numbe
21、r Course name Prerequisites C1 Programming I None C2 Discrete Mathematics None C4 Calculus I None C3 Data Structure C1,C2 C5 Calculus II C4 C6 Linear Algebra C5 C7 Analysis of Algorithms C3,C6 C15 Numerical Analysis C6 C8 Assembly Language C3 C10 Programming Languages C7 C9 Operating Systems C7,C8 C
22、12 Artificial Intelligence C7 C13 Computational Theory C7 C11 Compiler Design C10 C14 Parallel Algorithms C13 试着用试着用AOV图图表示出来表示出来求出给定求出给定DAG的一个拓扑序列，相当于进行一个作业调度。的一个拓扑序列，相当于进行一个作业调度。如何来求一个拓扑序列呢？如何来求一个拓扑序列呢？简单算法：简单算法：step 1 如果找得到任何一个入度为如果找得到任何一个入度为0的顶点的顶点v，则，则step 2，否则，否则step 4；step 2 输出顶点输出顶点v，并从图中删除该
23、顶点以及与其相连的所有边；，并从图中删除该顶点以及与其相连的所有边；step 3 对改变后的图重复这一过程，转对改变后的图重复这一过程，转step 1；step 4 如果已经输出全部顶点，则结束；否则该有向图不是如果已经输出全部顶点，则结束；否则该有向图不是DAG。理论依据是理论依据是基于基于下面的结论：一个顶点数下面的结论：一个顶点数|V|1的有向图的有向图，如果每个顶点的入度都大于，如果每个顶点的入度都大于0，那么它必定存在回路。，那么它必定存在回路。2 拓扑排序拓扑排序Note:对一个图来说，拓扑排序对一个图来说，拓扑排序不是唯一的。不是唯一的。如，要达到获得计如，要达到获得计算机科学学
24、位的条件有几种途径（拓扑排序）。算机科学学位的条件有几种途径（拓扑排序）。测试一个测试一个 AOV 的可行性，可能的话生成一个拓扑排序。的可行性，可能的话生成一个拓扑排序。void Topsort(Graph G)int Counter;Vertex V,W;for(Counter=0;Counter NumVertex;Counter+)V=FindNewVertexOfDegreeZero();if(V=NotAVertex)Error(“Graph has a cycle”);break;TopNum V =Counter;/*or output V*/for(each W adjace
25、nt to V)Indegree W ;/*O(|V|)*/T=O(|V|2)检查整个检查整个InDegree数组，数组，所需时间是所需时间是O(|V|)，此函数，此函数被调用被调用|V|次，故本算法的次，故本算法的时间复杂性为时间复杂性为 O(|V|2)2 拓扑排序拓扑排序 实现实现:将所有度为将所有度为0的未标记顶点放在一个特殊的盒子里（队列或栈）。的未标记顶点放在一个特殊的盒子里（队列或栈）。v1v2v6v7v3v4v5void Topsort(Graph G)Queue Q;int Counter=0;Vertex V,W;Q=CreateQueue(NumVertex);MakeEm
26、pty(Q);for(each vertex V)if(Indegree V =0)Enqueue(V,Q);while(!IsEmpty(Q)V=Dequeue(Q);TopNum V =+Counter;/*assign next*/for(each W adjacent to V)if(Indegree W =0)Enqueue(W,Q);/*end-while*/if(Counter!=NumVertex)Error(“Graph has a cycle”);DisposeQueue(Q);/*free memory*/0v1Indegree1v22v33v41v53v62v7v10v
27、212 10v50v41v60v320v71 0T=O(|V|+|E|)Mistakes in Fig 9.4【例例】交通的交通的最短路径最短路径 选择选择。最短路径有。最短路径有不同含义不同含义。3 最短路径算法最短路径算法给定一个图给定一个图G=(V,E),以及权值方程以及权值方程 c(e)，e E(G)。从从源点源点到到目标点目标点的路径的路径 P 的的长度长度是是 (也称也称带权路径带权路径长长)。Peiiec)(1.单源最短路径问题单源最短路径问题给定一个带权图给定一个带权图 G=(V,E),以及一个指定顶点以及一个指定顶点 s,找到找到从从 s 到图到图G其他所有顶点的最短带权路径
28、。其他所有顶点的最短带权路径。v1v2v6v7v3v4v52421310258461v1v2v6v7v3v4v52421310258461负值回路负值回路Note:如果没有负值如果没有负值回路，回路，从从 s 到到 s 的的最短路径定义为最短路径定义为 0。3 最短路径算法最短路径算法 无权最短路径无权最短路径v1v2v6v7v3v4v500:v31:v1 and v6112:v2 and v4223:v5and v733 算法梗概算法梗概广度优先搜索广度优先搜索 实现实现Table i.Dist:=distance from s to vi /*initialized to be excep
29、t for s*/Table i.Known:=1 if vi is checked;or 0 if notTable i.Path:=for tracking the path /*initialized to be 0*/3 最短路径算法最短路径算法void Unweighted(Table T)int CurrDist;Vertex V,W;for(CurrDist=0;CurrDist NumVertex;CurrDist+)for(each vertex V)if(!T V.Known&T V.Dist=CurrDist)T V.Known=true;for(each W adjac
30、ent to V)if(T W.Dist=Infinity)T W.Dist=CurrDist+1;T W.Path=V;/*end-if Dist=Infinity*/*end-if!Known&Dist=CurrDist*/*end-for CurrDist*/The worst case:v1v2v6v7v3v4v5v9v8 T=O(|V|2)如果如果 V 未标记，未标记，但但 Dist Infinity,那么那么 Dist 既不是既不是CurrDist 也不是也不是CurrDist+1.3 最短路径算法最短路径算法 改进算法改进算法void Unweighted(Table T)/*T
31、 is initialized with the source vertex S given*/Queue Q;Vertex V,W;Q=CreateQueue(NumVertex);MakeEmpty(Q);Enqueue(S,Q);/*Enqueue the source vertex*/while(!IsEmpty(Q)V=Dequeue(Q);T V.Known=true;/*not really necessary*/for(each W adjacent to V)if(T W.Dist=Infinity)T W.Dist=T V.Dist+1;T W.Path=V;Enqueue
32、(W,Q);/*end-if Dist=Infinity*/*end-while*/DisposeQueue(Q);/*free memory*/v1v2v6v7v3v4v50 v1Dist Path v20v3 v4 v5 v6 v70000000v3v71v3v11v3v61122v1v222v1v433v2v533v4T=O(|V|+|E|)为什么为什么?如果不是这样，那么如果不是这样，那么这条路径上必然存在顶点这条路径上必然存在顶点 w 不在不在 S 中。中。那么那么.3 最短路径算法最短路径算法 Dijkstra算法算法(带权最短路径算法带权最短路径算法)令令 S=s 与已经找到最短
33、路径的顶点与已经找到最短路径的顶点 vi对任意对任意 u S,定义定义 distance u =最小长度路径最小长度路径 s (vi S)u。如果路径都是按。如果路径都是按非降序非降序生成的，那么生成的，那么 最短路径必然最短路径必然只只经过经过 vi S;当当distance u =min w S|distance w ，(如果如果 u 不是唯一的，那么我们可在其中任选一顶点不是唯一的，那么我们可在其中任选一顶点);/*贪心贪心策略策略*/u 被选中被选中 如果如果 distance u1 distance u2 ，并且，并且 u1 被加入被加入 S,那么那么 distance u2 可能会
34、变化。如果是这样，从可能会变化。如果是这样，从 s 到到 u2 的一条更短的路径必定经过的一条更短的路径必定经过 u1，且，且 distance u2 =distance u1 +length().3 最短路径算法最短路径算法void Dijkstra(Table T)/*T is initialized by Figure 9.30 on p.303*/Vertex V,W;for(;)V=smallest unknown distance vertex;if(V=NotAVertex)break;T V.Known=true;for(each W adjacent to V)if(!T W
35、.Known)if(T V.Dist+Cvw T W.Dist)Decrease(T W.Dist to T V.Dist+Cvw);T W.Path=V;/*end-if update W*/*end-for(;)*/v1v2v6v7v3v4v524213102584610v1Dist Path v2 v3 v4 v5 v6 v700000002v11v13v43v49v45v48v36v7/*not work for edge with negative cost*/图图 9.31 实现了打印路径的例程。实现了打印路径的例程。/*O(|V|)*/3 最短路径算法最短路径算法 实现实现 1V
36、=最小的未知距离顶点；最小的未知距离顶点；/*简单地扫描表简单地扫描表 O(|V|)*/T=O(|V|2+|E|)如果图是稠密的，这种方法如果图是稠密的，这种方法较好较好 实现实现 2V=最小的未知距离顶点最小的未知距离顶点;/*将将distances放在优先队列里，并调用放在优先队列里，并调用 DeleteMin O(log|V|)*/Decrease(T W.Dist to T V.Dist+Cvw);/*方法方法 1:DecreaseKey O(log|V|)*/T=O(|V|log|V|+|E|log|V|)=O(|E|log|V|)/*方法方法 2:插入插入 W 已更新的已更新的Di
37、st 到优先队列到优先队列*/*必须连续执行必须连续执行 DeleteMin 知道一个未知顶点出现知道一个未知顶点出现*/如果图是稀疏的，如果图是稀疏的，这种方法较好这种方法较好T=O(|E|log|V|)但要求但要求|E|次次DeleteMin 及及|E|的空间。的空间。其他改进其他改进:配对堆配对堆(Ch.12)与与Fibonacci 堆堆(Ch.11)3 最短路径算法最短路径算法 具有负值边的图具有负值边的图Hey I have a good idea:why dont we simply add a constant to each edge and thus removenegati
38、ve edges?Too simple,and nave Try this one out:13422 221void WeightedNegative(Table T)/*T is initialized by Figure 9.30 on p.303*/Queue Q;Vertex V,W;Q=CreateQueue(NumVertex);MakeEmpty(Q);Enqueue(S,Q);/*Enqueue the source vertex*/while(!IsEmpty(Q)V=Dequeue(Q);for(each W adjacent to V)if(T V.Dist+Cvw T
39、 W.Dist)T W.Dist=T V.Dist+Cvw;T W.Path=V;if(W is not already in Q)Enqueue(W,Q);/*end-if update*/*end-while*/DisposeQueue(Q);/*free memory*/*negative-cost cycle will cause indefinite loop*/*no longer once per edge*/*each vertex can dequeue at most|V|times*/T=O(|V|E|)3 最短路径算法最短路径算法 无环图无环图如果图是无环的，顶点可以以
40、拓扑排序的顺序被选中。因为当一如果图是无环的，顶点可以以拓扑排序的顺序被选中。因为当一个顶点被选中，由于没有来自未知顶点的入边，它的个顶点被选中，由于没有来自未知顶点的入边，它的distance不可不可能再降低了。能再降低了。T=O(|E|+|V|)，不需要优先队列。，不需要优先队列。应用应用:AOE(Activity On Edge)Networks 规划一个项目规划一个项目vjai:=活动活动ai完成的标记完成的标记 EC j LC j :=顶点顶点 vj的最早的最早 最最迟完成时间迟完成时间 CPM(Critical Path Method，关键路径方法关键路径方法)持续时间持续时间松弛
41、时间松弛时间EC TimeLC Time 顶点编号顶点编号3 最短路径算法最短路径算法例例 一个虚拟项目的一个虚拟项目的AOE network012345678startfinisha0=6a1=4a2=5a3=1a4=1a5=2a6=9a7=7a8=4a9=2a10=4 计算计算EC:从从v0开始开始,对任意对任意ai=,我们有我们有max,),(wvEwvCvECwEC 064577161418a11=0哑活动哑活动 计算计算LC:从最后一个顶点从最后一个顶点v8开始开始,对任意对任意ai=,我们有我们有min,),(wvEwvCwLCvLC 181614775660 的的松弛时间松弛时间
42、=wvCvECwLC,232 关键路径关键路径:=全部由零松弛边组成的路径。全部由零松弛边组成的路径。3 最短路径算法最短路径算法2.所有顶点对间的最短路径问题所有顶点对间的最短路径问题对所有顶点对对所有顶点对 vi 和和 vj(i j),找到它们之间的最短路找到它们之间的最短路径。径。方法方法 1 使用使用单源最短路径算法单源最短路径算法|V|次。次。T=O(|V|3)在稀疏图上运行较快。在稀疏图上运行较快。方法方法 2 Ch.10给出了一个给出了一个O(|V|3)的算法的算法,在稠密图在稠密图上运行较快。上运行较快。4 网络流问题网络流问题例例 考虑如下管状网络：考虑如下管状网络：sdcb
43、at33322214源点源点汇点汇点Note:总计进入总计进入(v)的流量的流量 总计从总计从(v)流出的流量流出的流量 ，v s,t 找到图中从找到图中从 s 到到 t 的最大的最大流。流。4 网络流问题网络流问题1.简单的算法简单的算法sdcbat33322214GsdcbatFlow GfsdcbatResidual GrStep 1:找到图找到图Gr中的任意路径中的任意路径 s t;增长路径增长路径Step 2:将路径中的最小边作为路将路径中的最小边作为路径的流量，并添加路径到径的流量，并添加路径到 Gf;Step 3:更新更新 Gr 并移去并移去 0 流量的边流量的边;Step 4:
44、If(Gr存在路径存在路径 s t )Goto Step 1;Else End.对了对了!如果我先选择路径如果我先选择路径s a d t，会怎样呢会怎样呢?实际上很简单。但是我希望实际上很简单。但是我希望你在这儿能指出一些问题。你在这儿能指出一些问题。呃呃 看起来我们在这儿看起来我们在这儿不能使用不能使用贪婪策略贪婪策略。4 网络流问题网络流问题sdcbat33322214G4 网络流问题网络流问题2.一个解决办法一个解决办法 允许算法允许算法撤销撤销它的选择它的选择对对Gf中的每一条边中的每一条边(v,w)，流值为，流值为fv,w，在，在Gr中添加一条流值为中添加一条流值为 fv,w 的边的
45、边。sdcbatFlow Gfsdcbat33322214GsdcbatResidual Gr333222143333313222222213221Proposition 如果边的容量是如果边的容量是有理数有理数，这个算法将总是在最，这个算法将总是在最大流终止。大流终止。Note:算法对算法对有环有环的的图依然有效。图依然有效。4 网络流问题网络流问题3.分析分析(如果容量都是整数如果容量都是整数)一条增长路径可以用无权最短路径算法找出。一条增长路径可以用无权最短路径算法找出。T=O()，f 是最大流。是最大流。f|E|stab1 000 0001 000 0001 000 0001 000
46、0001 总是选择那些使得流增长最大的路径。总是选择那些使得流增长最大的路径。/*修改修改 Dijkstra算法算法*/T=Taugmentation*Tfind a path=O(|E|log capmax)*O(|E|log|V|)=O(|E|2 log|V|)if capmax is a small integer.4 网络流问题网络流问题 总是选择具有最少边数的增长路径。总是选择具有最少边数的增长路径。T=Taugmentation*Tfind a path=O(|E|)*O(|E|V|)=O(|E|2|V|)/*无权最短路径算法无权最短路径算法*/Note:如果每个如果每个v s,t
47、 拥有一条容量为拥有一条容量为1的入边或一条容量为的入边或一条容量为1的出的出边，那么时间界将减少到边，那么时间界将减少到 O(|E|V|1/2).最小值流问题最小值流问题是要在所有最大流中找出具有最小权值的流。在是要在所有最大流中找出具有最小权值的流。在这种问题中，每条边拥有一个权值。这种问题中，每条边拥有一个权值。5 最小生成树最小生成树【定义定义】一棵图一棵图 G 的的生成树生成树 是一棵由是一棵由V(G)和和E(G)的子的子集集构成的树。构成的树。例例 一个完全图和三棵生成树。一个完全图和三棵生成树。Note:最小生成树最小生成树 是一棵是一棵树树，因此它无环，因此它无环 边数是边数是
48、|V|1.它是它是最小最小的，因为边的总权值最小。的，因为边的总权值最小。它是它是生成树生成树，因为包含了图的所有顶点。，因为包含了图的所有顶点。最小生成树最小生成树 存在，当且仅当存在，当且仅当 G 是是连通的连通的。向一棵生成树添加一条非树中的边，将得到一个向一棵生成树添加一条非树中的边，将得到一个环环。5 最小生成树最小生成树在以下约束条件下，每个阶段都做出当前最好的在以下约束条件下，每个阶段都做出当前最好的选择选择:(1)必须使用图中的边；必须使用图中的边；(2)必须使用恰好必须使用恰好|V|1 条边；条边；(3)不能使用会产生环的边。不能使用会产生环的边。1.Prim算法算法 gro
49、w a tree/*与与Dijkstra算法非常相似算法非常相似*/v1v2v6v7v3v4v524213107584615 最小生成树最小生成树2.Kruskal算法算法 maintain a forestvoid Kruskal(Graph G)T=;while (T contains less than|V|1 edges&E is not empty)choose a least cost edge(v,w)from E;delete(v,w)from E;if (v,w)does not create a cycle in T)add(v,w)to T;else discard(v,
50、w);if (T contains fewer than|V|1 edges)Error(“No spanning tree”);/*DeleteMin*/*Union/Find*/更详细的伪代码在图更详细的伪代码在图 9.58中给出中给出T=O(|E|log|E|)7 NP-完全性介绍完全性介绍 回顾回顾:单源无权最短路径问题单源无权最短路径问题 单源无权最长路径问题单源无权最长路径问题 没有没有 已知算法能在已知算法能在多项式时间多项式时间内解决内解决7 NP-完全性完全性【例例】停机问题停机问题:是否能让是否能让C编译器检查所有的编译器检查所有的无限循环无限循环？回答回答:No.证明证明
