图的基本算法.ppt

1、图的基本算法,Company Logo,图的一些基本概念及其表示,Contents,拓扑排序和欧拉回路问题,最小生成树和单源最短路问题,二分图匹配,1,2,3,4,Company Logo,定义与术语,图：二元组 称为图(graph)。 V为结点(node)点(vertex)集。 E为中结点之间的边的集合。 子图：什么是子图如果有两个图G和G，G的顶点集是G的顶点集的子集，且G的边集 点对(u,v)称为边(edge)或称弧(arc)，其中 u,v属于V，称 u,v 是相邻的(adjacent)，称u,v与边 相关联(incident)。 连通图：如果图中任意一对顶点都有路径存在，则称该图为连通

2、的,Company Logo,定义与术语,若边的点对(u,v) 有序则称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。所形成的图称有向图(directed graph)。为对于u来说 是出边(outgoing arc)；对于v来说 是入边(incoming arc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirected graph)。,Company Logo,定义与术语,度(degree):一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v)。无向图： 有向图： 入度(indegree):在有向图中，

3、一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数。 出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数 。 路径：如果从一个顶点v1出发，沿着一些边依次经过一些定点v2,v3,vn,则称顶点序列(v1,v2,.,vn)为从顶点v1到vn的路径。 回路：如果一条路径上第一个顶点和最后一个顶点是相同的，则称这样的路径为回路或环。,Company Logo,图的表示,要表示一个图G=(V,E),有两种标准的方法，即邻接表和邻接矩阵。这两种方法即可以用于有向图，也可以用于无向图。,用邻接表记录图,Struct Edge int dest;/记

4、录目的地 int value;/边的权值 Edge* link;/记录链表的下一个元素 ; Edge *edge=new Edgen;/申请空间 for(int i=0;iuv)/ (u,v)表示一条边 L=new Edge; L-dest=v;/填写目的地 L-link=edgeu;/用新建的这条边指向顶点u指向的链表 edgeu=L;/再把L赋给edgeu ,Company Logo,遍历邻接表,for(int i=0;idestlink;/取链表的下一个元素 ,Company Logo,Company Logo,DFS，BFS 拓扑排序 强连通分支 欧拉路径和回路 最小生成树 最短路径

5、哈密顿回路(NP) 差分约束系统 网络流 二分图匹配,图论涉及到的问题和算法,Company Logo,今天要讲的问题,最小生成树 最短路算法,拓扑排序 欧拉回路,二分图的匹配,拓扑排序,拓扑排序是对有向无回路图(DAG)顶点的一种排序，它使得如果存在u,v的有向路径，那么满足序中u在v前。拓扑排序就是由一种偏序(partical order)得到一个全序(称为拓扑有序(topological order)。偏序是满足自反性，反对称性，传递性的序。 一个图的拓扑排序得到的结果可以看成是图中所有顶点沿水平线排列而成的序列，而且所有的有向边均是从左指向右 在有向无回路图用于说明事件发生的先后顺序

6、拓扑排序可以给出一个满足时间先后的顺序,Company Logo,陈熙大牛穿衣服的例子,Company Logo,拓扑排序算法描述,拓扑排序的思路很简单，就是每次任意找一个入度为0的点输出，并把这个点以及与这个点相关的边删除。实际算法中，用一个队列实现。 算法： 1.把所有入度=0的点入队Q。 2.若队Q非空，则点u出队，输出u；否则转4。 3.把所有与点u相关的边(u,v)删除，若此过程中有点v的入度变为0，则把v入队Q，转2。 4.若出队点数N，则说明有圈。 时间复杂度O(V+E),Company Logo,欧拉回路,欧拉回路，又称“一笔画”，是图论中可行遍性问题的一种 欧拉回路问题是图论

7、中最古老的问题之一。它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞格尔河流经这座城市，人们在两岸以及河中间的两个小岛之间建了七座桥。 市民们喜欢在这里散步，于是产生了这样一个问题：是否可以找到一种方案，使得人们从自己家里出发，不重复地走遍每一座桥，然后回到家中？这个问题如果用数学语言来描述，就是在右图中找出一条回路，使得它不重复地经过每一条边。这便是著名的“哥尼斯堡七桥问题”。,Company Logo,一些概念及定理,欧拉回路:图G中经过每条边一次并且仅一次的回路称作欧拉回路。 欧拉路径:图G中经过每条边一次并且仅一次的路径称作欧拉路径。 欧拉图:存在欧拉回路的图称为欧拉图。 半欧拉图存在欧拉路径

8、但不存在欧拉回路的图称为半欧拉图。 我们经常需要判定一个图是否为欧拉图（或半欧拉图），并且找出一条欧拉回路（或欧拉路径）。对于无向图有如下结论： 定理1无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。,Company Logo,一些概念及定理,推论1无向图 为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。 定理2有向图 为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出度。 推论2有向图 为半欧拉图，当且仅当G的基图连通，且存在顶点 的入度比出度大1、 的入度比出度小1，其它所有顶点的入度等于出度。 基图：忽略有向图所有边的方向，得到的无向图称

9、为该有向图的基图。,Company Logo,欧拉回路算法描述,由此可以得到以下求欧拉图 的欧拉回路的算法： 在图G中任意找一个回路 ； 将图G中属于回路 的边删除； 在残留图的各极大连通子图中分别寻找欧拉回路； 将各极大连通子图的欧拉回路合并到 中得到图 的欧拉回路。,Company Logo,算法描述,Procedure Euler-circuit ( ); Begin For顶点start的每个邻接点v Do If 边(start,v)未被标记 Then Begin 将边(start,v)作上标记; 将边(v,start)作上标记; Euler-circuit (v); 将边 (star

10、t,v)加入栈 ; End; End; 最后依次取出栈S每一条边而得到图G的欧拉回路。 由于该算法执行过程中每条边最多访问两次，因此该算法的时间复杂度为 O(E)。,Company Logo,例题,例题一单词游戏 题目描述有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。 数据规模 N=100000 分析通过对题目条件的一些初步分析，我们很容易得到下面的模型。,Company Logo,分析,模型1：以

11、 N个盘子作为顶点；如果盘子A的末字母等于盘子B的首字母，那么从A向B连一条有向边。对于样例我们可以按下图所示的方式构图。这样，问题转化为在图中寻找一条不重复地经过每一个顶点的路径，即哈密尔顿路。然而，求哈密尔顿路是一个十分困难的问题，这样的模型没有给我们的解题带来任何便利。因此，我们必须另辟蹊径。,Company Logo,分析,模型2：经过分析，我们发现模型1的失败之处在于，图中需要遍历的信息也就是每一个盘子表示在顶点上，而顶点的遍历问题不易解决。能否将遍历信息表示在边上呢？考虑如下的构图方法：以26个字母作为顶点；对于每一个盘子，如果它的首字母为c1，末字母为c2，那么从c1向c2连一条

12、有向边。对于样例我们可以按下图所示的方式构图这样，问题转化为在图中寻找一条不重复地经过每一条边的路径，即欧拉路径。这个问题能够在O(E)时间内解决。,Company Logo,最小生成树,在电路设计中，常常需要把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚，把所有n个插脚连接起来，只要用n-1根电线就可以了。在 所有的连接方案中，我们通常对电线总长度最小的连接方案感兴趣。 把问题转化为图论模型就是：一个无向连通图G=(V,E)，V是插脚的集合，E是插脚两两之间所有可能的连接的集合。给每条边(u,v)一个权值w(u,v)，表示连接它们所需的电线长度。我们的目标就是找到一个无环的边集

13、T，连接其中所有的点且使总权值最小。 既然T 是连接所有点的无环边集，它一定是一棵树。因为这棵树是从图G中生成出来的，我们把它叫做生成树。如果一棵生成树在所有生成树中总权值最小，我们就把它称作最小生成树。,Company Logo,Kruskal,MST-KRUSKAL(G,w) 1. A 2. for 每个结点vVG 3. do MAKE-SET(v) 4. 根据权w的非递减顺序对E的边进行排序 5. for 每条边(u,v)E，按权的非递减次序 6. do if FIND-SET(u)FIND-SET(v) 7. then AA(u,v) 8. UNION(u,v) 9. return A

14、 复杂度E*lgE,Company Logo,步骤,Company Logo,步骤,Company Logo,步骤,Company Logo,步骤,Company Logo,Prim算法,Kruskal找出连接任意两棵树的所有边中，具有最小权值的边(u,v)，把它添加到正在生长的森林中。 Prim的特点它一直维持生成单棵树，而Kruskal生成时可以存在多个树。 Prim每次选一个点加入到集合中，直到把所有点都加入到集合中,Company Logo,算法描述,MST-PRIM(G,w,r) 1. QVG 2. for 每个uQ 3. do keyu 4. keyr0 5. rNIL 6. wh

15、ile Q 7. do uEXTRACT-MIN(Q) 返回队列Q中最小的元素 8. for 每个vAdju 9. do if vQ and w(u,v)keyv 10. then vu 11. keyvw(u,v),Company Logo,执行过程,Company Logo,执行过程,Company Logo,执行过程,Company Logo,最短路概述,最短路问题是图论中的核心问题之一，它是许多更深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题 乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地

16、图上标出了每对十字路口之间的距离，如何找出这一最短行程？ 在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。,Company Logo,最短路概述,我们一般所将的都是单源最短路径问题，即我们希望找出从某给定点s到每个顶点的最短路径。 不过有许多其他的问题也可以用最短路算法解决 单目标最短路径问题： 找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。 单对结点间的最短路径问题：对于某给定结点u和v，找出从u到v的一条最短路径

17、。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决 每对结点间的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。,Company Logo,最短路涉及到的问题,负权边值：在某些最短路的实例中，可能存在权值为负的边。如果存在一条从s可达的负权回路，那么最短路的权的定义就不能存在了。 因为只要穿越负权回路任意次我们就可以发现从s到e可以无限变小。,Company Logo,最短路涉及到的问题,回路：一条最短路径能包含回路吗？它不能包含负权回路。它也不会包含正权回路，因为从路径上移去回路后回路后可以产生一个具有相同源点

18、和终点，权值更小的路径。,Company Logo,松弛技术,对于每个顶点v,都设置了一个属性dv,用来描述从源点s到v的最短路的上界，称为最短路径估计。 init() for(int i=0;idu+w) dv=du+w; prev=u; 三角不等式：对于任意边(u,v)，有(s, v) (s, u) + w(u, v).,Company Logo,Company Logo,最短路算法,Dijkstra,SPFA,Bellman Ford,最短路算法,最短路算法,我们着重讨论两种常用算法：Dijkstra算法和Bellman-Ford算法。虽然它们都是建立在松弛技术基础上的算法，但是在实现上

19、有着各自的特点，适用的范围也有所不同。 另外，我们还将介绍一种期望复杂度与边数同阶的高效算法SPFA算法，并对其复杂度作出简要的分析。,Company Logo,Dijkstra,Dijkstra算法解决了有向加权图的最短路径问题，该算法的条件是该图所有边的权值非负，因此在本小节我们约定：对于每条边(u,v) E，w(u,v)=0。 Dijkstra算法中设置了一结点集合S，从源结点s到集合S中结点的最终最短路径的权均已确定，即对所有结点v属于S，有dv已经为最小。算法反复挑选出其最短路径估计为最小的结点u属于V-S，把u插入集合S中，并对离开u的所有边进行松弛,Company Logo,Di

20、jkstra算法描述,Dijkstra(G,w,s) INIT (G,S) S =NULL Q=VG While Q Do u=EXTRACT-MIN(Q) S=S Uu For 每个顶点v Adju Do RELAX(u,v,w),Company Logo,算法执行过程,Company Logo,Bellman-Ford,Bellman-Ford算法 Bellman-Ford算法能在更一般的情况下解决单源点最短路径问题，在该算法下边的权可以为负。正如Dijkstra算法一样，Bellman-Ford算法运用了松弛技术，对每一结点v ，逐步减小从源s到v的最短路径的估计值dv直至其达到实际最短

21、路径的权 (s,v)，如果图中存在负权回路，算法将会报告最短路不存在。 Bellman-Ford算法可以用于解决差分约束系统,Company Logo,算法描述,Bellman-Ford(G,w,s) init(G,s) For i 1 to |VG|-1 Do For 每条边(u,v) EG Do RELAX(u,v,w) For每条边(u,v) EG Do If dv du + w(u, v) Then Return FALSE Return TRUE 时间复杂度为O(V*E);,Company Logo,执行过程,Company Logo,Bellman-Ford思想,Bellman-F

22、ord算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值） 根据最短路的最优子结构，路径边数上限为k时的最短路可以由边数上限为k-1时的最短路“加一条边”来求，而根据刚才的结论，最多只需要迭代n-1次就可以求出最短路。,Company Logo,SPFA,Shortestpathfasteralgorithm SPFA 其实就是Bellman-Ford的一种队列实现，减少了冗余，即松驰的边至少不会以一个

23、d为的点为起点。 算法： 1.队列Q=s， ， 2.取出队头u,枚举所有的u的临边 .若d(v)d(u)+w(u,v)则改进 ，pre(v)=u，由于d(v)减少了，v可能在以后改进其他的点，所以若v不在Q中，则将v入队。 3.一直迭代2，直到队列Q为空(正常结束)，或有的点的入队次数=n（含有负圈）。,Company Logo,SPFA算法分析,一般用于找负圈(效率高于Bellman-Ford)，稀疏图的最短路 由于点可能多次入队，但队列中同时不会超过n个点。所以用一个长度为n的循环队列来实现这个队。 SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进

24、入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的（不含负圈，较稀疏）情况，k在2左右。算法复杂度理论上同Bellman-Ford，O(nm)，但实际上却是O(km)。,Company Logo,例题,例题1货币兑换（pku1860|zju1544） 若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率，货币A到货币B的汇率表

25、示要多少单位的货币B才能兑换到一个单位的货币A。当然货币兑换要支付一定量的中转费。 例如，如果你想将100美元兑换成俄元，汇率是29.75，中转费为0.39， 那么你会兑换到(100-0.39)29.75=2963.3975俄元。,Company Logo,例题,城市中流通着N(N=100)类货币，用数字1至N标号表示。每个货币兑换点用6个数字来描述：整数A和B是兑换货币的编号，实数RAB，CAB，RBA，CBA分别是A兑换成B和B兑换成A的汇率和中转费用。 Nick有一些第S类货币，他想在若干次交换后增加他的资金，当然这些资金最终仍是第S类货币。请你告诉他该想法能否实现 Sample Inp

26、ut 3 2 1 20.0 /货币数量,兑换点数量,初始货币编号资金 1 2 1.00 1.00 1.00 1.00/A,B,Rab,Rba,Cab,Cba 2 3 1.10 1.00 1.10 1.00 Sample Output YES,Company Logo,分析,如果我们可以求出，通过一系列的兑换 每种货币可以得到的最大值，那么问题便迎刃而解了。 因为要是可以得到的第S类货币最大值都不比初值大，资金肯定无法增加；否则，得到最大值的过程就是一种解法。 到了这里，我们发现求最大值和我们学过的求最短路很类似，构图用最短路算法做也显得水到渠成了。 具体做法是： 将N种货币看成N个结点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A货币兑换到B货币的汇率和中转费用为RAB，CAB，那么由对应的A结点向B结点连一条有向边，从A点得到的B的可能最大值为：(A目前的最大值-CAB)RAB。,Company Logo,分析,注意，这里所求的是最大值，为了转化为最短路，我们可以在数字前面加上一个负号。 更简洁的方法是利用求最短路的方法，求最长路。 由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，我们可以用Bellman-Ford算法或者SPFA算法做，这里用Bellman-For