图的基本算法幻灯片.ppt

《图的基本算法幻灯片.ppt》由会员分享，可在线阅读，更多相关《图的基本算法幻灯片.ppt（57页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图图的基本算法的基本算法第1页，共57页，编辑于2022年，星期五Company Logo 图的一些基本概念及其表示Contents拓扑排序和拓扑排序和欧欧拉回路拉回路问题最小生成最小生成树和和单源最短路源最短路问题二分二分图匹配匹配1234第2页，共57页，编辑于2022年，星期五Company Logo定义与术语v图：二元组称为图(graph)。V为结点(node)点(vertex)集。E为中结点之间的边的集合。v子图：什么是子图如果有两个图G和G，G的顶点集是G的顶点集的子集，且G的边集v点对(u,v)称为边(edge)或称弧弧(arc)，其中u,v属于V，称u,v是相相邻的(adjac

2、ent)，称u,v与边相关关联(incident)。v连通图：如果图中任意一对顶点都有路径存在，则称该图为连通的第3页，共57页，编辑于2022年，星期五Company Logo定义与术语v若边的点对(u,v)有序则称为有向有向(directed)边，其中u称为头(head)，v称为尾尾(tail)。所形成的图称有向有向图(directedgraph)。为对于u来说是出出边(outgoingarc)；对于v来说是入入边(incomingarc)。反之，若边的点对无序则称为无向无向(undirected)边，所形成的图称无向无向图(undirectedgraph)。第4页，共57页，编辑于202

3、2年，星期五Company Logo定义与术语v度度(degree):一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v)。无向图：有向图：v入度入度(indegree):在有向图中，一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数。v出度出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数。v路径：如果从一个顶点v1出发，沿着一些边依次经过一些定点v2,v3,vn,则称顶点序列(v1,v2,.,vn)为从顶点v1到vn的路径。v回路：如果一条路径上第一个顶点和最后一个顶点是相同的，则称这样的路径为回路或环。第5页，共57

4、页，编辑于2022年，星期五Company Logo图的表示要表示一个图G=(V,E),有两种标准的方法，即邻接表和邻接矩阵。这两种方法即可以用于有向图，也可以用于无向图。第6页，共57页，编辑于2022年，星期五用邻接表记录图StructEdgeintdest;/记录目的地intvalue;/边的权值Edge*link;/记录链表的下一个元素;Edge*edge=newEdgen;/申请空间for(inti=0;iuv)/(u,v)表示一条边L=newEdge;L-dest=v;/填写目的地L-link=edgeu;/用新建的这条边指向顶点u指向的链表edgeu=L;/再把L赋给Compan

5、y Logo第7页，共57页，编辑于2022年，星期五遍历邻接表for(inti=0;in;i+)L=edgei;/取得邻接表的链表入口while(L!=NULL)/输出从顶点i出发可以到达的边couti“”destlink;/取链表的下一个元素Company Logo第8页，共57页，编辑于2022年，星期五Company LogovDFS，BFSv拓扑排序拓扑排序v强强连通分支通分支 v欧欧拉路拉路径径和回路和回路v最小生成最小生成树v最短路最短路径径v哈密哈密顿回路回路(NP)v差分差分约束系束系统v网网络流流v二分二分图匹配匹配图论涉及到的问题和算法第9页，共57页，编辑于2022年，

6、星期五Company Logo今天要讲的问题最小生成树最短路算法拓扑排序欧拉回路 二分图的匹配第10页，共57页，编辑于2022年，星期五拓扑排序v拓扑排序是对有向无回路图(DAG)顶点的一种排序，它使得如果存在u,v的有向路径，那么满足序中u在v前。拓扑排序就是由一种偏序(particalorder)得到一个全序(称为拓扑有序(topologicalorder)。偏序是满足自反性，反对称性，传递性的序。v一个图的拓扑排序得到的结果可以看成是图中所有顶点沿水平线排列而成的序列，而且所有的有向边均是从左指向右v在有向无回路图用于说明事件发生的先后顺序v拓扑排序可以给出一个满足时间先后的顺序Com

7、pany Logo第11页，共57页，编辑于2022年，星期五陈熙大牛穿衣服的例子Company Logo第12页，共57页，编辑于2022年，星期五拓扑排序算法描述v拓扑排序的思路很简单，就是每次任意找一个入度为0的点输出，并把这个点以及与这个点相关的边删除。实际算法中，用一个队列实现。v算法：1.把所有入度=0的点入队Q。2.若队Q非空，则点u出队，输出u；否则转4。3.把所有与点u相关的边(u,v)删除，若此过程中有点v的入度变为0，则把v入队Q，转2。4.若出队点数N，则说明有圈。时间复杂度O(V+E)Company Logo第13页，共57页，编辑于2022年，星期五欧拉回路v欧拉回

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

9、径欧拉路径:图G中经过每条边一次并且仅一次的路径称作欧拉路径。v欧拉欧拉图:存在欧拉回路的图称为欧拉图。v半欧拉半欧拉图存在欧拉路径但不存在欧拉回路的图称为半欧拉图。v我们经常需要判定一个图是否为欧拉图（或半欧拉图），并且找出一条欧拉回路（或欧拉路径）。对于无向图有如下结论：v定理定理1无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。Company Logo第15页，共57页，编辑于2022年，星期五一些概念及定理v推推论1无向图为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。v定理定理2有向图为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出

10、度。v推推论2有向图为半欧拉图，当且仅当G的基图连通，且存在顶点的入度比出度大1、的入度比出度小1，其它所有顶点的入度等于出度。基图：忽略有向图所有边的方向，得到的无向图称为该有向图的基图。Company Logo第16页，共57页，编辑于2022年，星期五欧拉回路算法描述v由此可以得到以下求欧拉图的欧拉回路的算法：v在图G中任意找一个回路；v将图G中属于回路的边删除；v在残留图的各极大连通子图中分别寻找欧拉回路；v将各极大连通子图的欧拉回路合并到中得到图的欧拉回路。Company Logo第17页，共57页，编辑于2022年，星期五算法描述vProcedureEuler-circuit();

11、vBeginvFor顶点start的每个邻接点vDovIf边(start,v)未被标记ThenBegin将边(start,v)作上标记;将边(v,start)作上标记;Euler-circuit(v);将边(start,v)加入栈;vEnd;vEnd;v最后依次取出栈S每一条边而得到图G的欧拉回路。v由于该算法执行过程中每条边最多访问两次，因此该算法的时间复杂度为O(E)。Company Logo第18页，共57页，编辑于2022年，星期五例题v例例题一一单词游游戏v题目描述目描述有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，

12、前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。v数据数据规模模N=100000v分析分析通过对题目条件的一些初步分析，我们很容易得到下面的模型。Company Logo第19页，共57页，编辑于2022年，星期五分析v模型1：以N个盘子作为顶点；如果盘子A的末字母等于盘子B的首字母，那么从A向B连一条有向边。对于样例我们可以按下图所示的方式构图。这样，问题转化为在图中寻找一条不重复地经过每一个顶点的路径，即哈密尔顿路。然而，求哈密尔顿路是一个十分困难的问题，这样的模型没有给我们的解题带来任何便利。因此，我们必须

13、另辟蹊径。Company Logo第20页，共57页，编辑于2022年，星期五分析v模型2：经过分析，我们发现模型1的失败之处在于，图中需要遍历的信息也就是每一个盘子表示在顶点上，而顶点的遍历问题不易解决。能否将遍历信息表示在边上呢？考虑如下的构图方法：以26个字母作为顶点；对于每一个盘子，如果它的首字母为c1，末字母为c2，那么从c1向c2连一条有向边。对于样例我们可以按下图所示的方式构图这样，问题转化为在图中寻找一条不重复地经过每一条边的路径，即欧拉路径。这个问题能够在O(E)时间内解决。Company Logo第21页，共57页，编辑于2022年，星期五最小生成树v在电路设计中，常常需要

14、把一些电子元件的插脚用电线连接起来。如果每根电线连接两个插脚，把所有n个插脚连接起来，只要用n-1根电线就可以了。在v所有的连接方案中，我们通常对电线总长度最小的连接方案感兴趣。v把问题转化为图论模型就是：一个无向连通图G=(V,E)，V是插脚的集合，E是插脚两两之间所有可能的连接的集合。给每条边(u,v)一个权值w(u,v)，表示连接它们所需的电线长度。我们的目标就是找到一个无环的边集T，连接其中所有的点且使总权值最小。v既然T是连接所有点的无环边集，它一定是一棵树。因为这棵树是从图G中生成出来的，我们把它叫做生成生成树。如果一棵生成。如果一棵生成树在所有生成在所有生成树中中总权值最最小，我

15、们就把它称作最小生成最小生成树。Company Logo第22页，共57页，编辑于2022年，星期五KruskalvMST-KRUSKAL(G,w)v1.Av2.for每个结点vVGv3.doMAKE-SET(v)v4.根据权w的非递减顺序对E的边进行排序v5.for每条边(u,v)E，按权的非递减次序v6.doifFIND-SET(u)FIND-SET(v)v7.thenAA(u,v)v8.UNION(u,v)v9.returnAv复杂度E*lgECompany Logo第23页，共57页，编辑于2022年，星期五步骤Company Logo第24页，共57页，编辑于2022年，星期五步骤C

16、ompany Logo第25页，共57页，编辑于2022年，星期五步骤Company Logo第26页，共57页，编辑于2022年，星期五步骤Company Logo第27页，共57页，编辑于2022年，星期五Prim算法vKruskal找出连接任意两棵树的所有边中，具有最小权值的边(u,v)，把它添加到正在生长的森林中。vPrim的特点它一直维持生成单棵树，而Kruskal生成时可以存在多个树。vPrim每次选一个点加入到集合中，直到把所有点都加入到集合中Company Logo第28页，共57页，编辑于2022年，星期五算法描述vMST-PRIM(G,w,r)v1.QVGv2.for每个u

17、Qv3.dokeyuv4.keyr0v5.rNILv6.whileQv7.douEXTRACT-MIN(Q)返回队列Q中最小的元素v8.for每个vAdjuv9.doifvQandw(u,v)keyvv10.thenvuv11.keyvw(u,v)Company Logo第29页，共57页，编辑于2022年，星期五执行过程Company Logo第30页，共57页，编辑于2022年，星期五执行过程Company Logo第31页，共57页，编辑于2022年，星期五执行过程Company Logo第32页，共57页，编辑于2022年，星期五最短路概述v最短路问题是图论中的核心问题之一，它是许多更

18、深层算法的基础。同时，该问题有着大量的生产实际的背景。不少问题从表面上看与最短路问题没有什么关系，却也可以归结为最短路问题v乘汽车旅行的人总希望找出到目的地尽可能短的行程。如果有一张地图并在地图上标出了每对十字路口之间的距离，如何找出这一最短行程？v在乘车旅行的例子中，我们可以把公路地图模型化为一个图：结点表示路口，边表示连接两个路口的公路，边权表示公路的长度。我们的目标是从起点出发找一条到达目的地的最短路径。Company Logo第33页，共57页，编辑于2022年，星期五最短路概述v我们一般所将的都是单源最短路径问题，即我们希望找出从某给定点s到每个顶点的最短路径。v不过有许多其他的问题

19、也可以用最短路算法解决v单目目标最短路径最短路径问题：找出从每一结点v到某指定结点u的一条最短路径。把图中的每条边反向，我们就可以把这一问题转化为单源最短路径问题。v单对结点点间的最短路径的最短路径问题：对于某给定结点u和v，找出从u到v的一条最短路径。如果我们解决了源结点为u的单源问题，则这一问题也就获得了解决v每每对结点点间的最短路径的最短路径问题：对于每对结点u和v，找出从u到v的最短路径。我们可以用单源算法对每个结点作为源点运行一次就可以解决问题。Company Logo第34页，共57页，编辑于2022年，星期五最短路涉及到的问题v负权边值：在某些最短路的实例中，可能存在权值为负的边

20、。如果存在一条从s可达的负权回路，那么最短路的权的定义就不能存在了。v因为只要穿越负权回路任意次我们就可以发现从s到e可以无限变小。Company Logo第35页，共57页，编辑于2022年，星期五最短路涉及到的问题v回路：一条最短路径能包含回路吗？它不能包含负权回路。它也不会包含正权回路，因为从路径上移去回路后回路后可以产生一个具有相同源点和终点，权值更小的路径。Company Logo第36页，共57页，编辑于2022年，星期五松弛技术v对于每个顶点v,都设置了一个属性dv,用来描述从源点s到v的最短路的上界，称为最短路径估计。vinit()for(inti=0;idu+w)dv=du+

21、w;prev=u;三角不等式：对于任意边(u,v)，有(s,v)(s,u)+w(u,v)Company Logo第37页，共57页，编辑于2022年，星期五Company Logo最短路算法DijkstraSPFABellmanFord最短路算法最短路算法第38页，共57页，编辑于2022年，星期五最短路算法v我们着重讨论两种常用算法：Dijkstra算法和Bellman-Ford算法。虽然它们都是建立在松弛技术基础上的算法，但是在实现上有着各自的特点，适用的范围也有所不同。v另外，我们还将介绍一种期望复杂度与边数同阶的高效算法SPFA算法，并对其复杂度作出简要的分析。Company Logo

22、第39页，共57页，编辑于2022年，星期五DijkstravDijkstra算法解决了有向加权图的最短路径问题，该算法的条件是该图所有边的权值非负，因此在本小节我们约定：对于每条边(u,v)E，w(u,v)=0。vDijkstra算法中设置了一结点集合S，从源结点s到集合S中结点的最终最短路径的权均已确定，即对所有结点v属于S，有dv已经为最小。算法反复挑选出其最短路径估计为最小的结点u属于V-S，把u插入集合S中，并对离开u的所有边进行松弛Company Logo第40页，共57页，编辑于2022年，星期五Dijkstra算法描述vDijkstra(G,w,s)vINIT(G,S)vS=N

23、ULLvQ=VGvWhileQvDou=EXTRACT-MIN(Q)vS=SUuvFor每个顶点vAdjuvDoRELAX(u,v,w)Company Logo第41页，共57页，编辑于2022年，星期五算法执行过程Company Logo第42页，共57页，编辑于2022年，星期五Bellman-Fordv Bellman-Ford算法算法vBellman-Ford算法能在更一般的情况下解决单源点最短路径问题，在该算法下边的权可以为负。正如Dijkstra算法一样，Bellman-Ford算法运用了松弛技术，对每一结点v，逐步减小从源s到v的最短路径的估计值dv直至其达到实际最短路径的权(s

24、,v)，如果图中存在负权回路，算法将会报告最短路不存在。vBellman-Ford算法可以用于解决差分约束系统Company Logo第43页，共57页，编辑于2022年，星期五算法描述vBellman-Ford(G,w,s)vinit(G,s)vFori1to|VG|-1vDoFor每条边(u,v)EGvDoRELAX(u,v,w)vFor每条边(u,v)EGvDoIfdvdu+w(u,v)vThenReturnFALSEvReturnTRUEv时间复杂度为O(V*E);Company Logo第44页，共57页，编辑于2022年，星期五执行过程Company Logo第45页，共57页，编

25、辑于2022年，星期五Bellman-Ford思想vBellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）v根据最短路的最优子结构，路径边数上限为k时的最短路可以由边数上限为k-1时的最短路“加一条边”来求，而根据刚才的结论，最多只需要迭代n-1次就可以求出最短路。Company Logo第46页，共57页，编辑于2022年，星期五SPFAvShortestpathfasteral

26、gorithmvSPFA其实就是Bellman-Ford的一种队列实现，减少了冗余，即松驰的边至少不会以一个d为的点为起点。v算法：v1.队列Q=s，v2.取出队头u,枚举所有的u的临边.若d(v)d(u)+w(u,v)则改进，pre(v)=u，由于d(v)减少了，v可能在以后改进其他的点，所以若v不在Q中，则将v入队。v3.一直迭代2，直到队列Q为空(正常结束)，或有的点的入队次数=n（含有负圈）。Company Logo第47页，共57页，编辑于2022年，星期五SPFA算法分析v一般用于找负圈(效率高于Bellman-Ford)，稀疏图的最短路v由于点可能多次入队，但队列中同时不会超过n

27、个点。所以用一个长度为n的循环队列来实现这个队。vSPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的（不含负圈，较稀疏）情况，k在2左右。算法复杂度理论上同Bellman-Ford，O(nm)，但实际上却是O(km)。Company Logo第48页，共57页，编辑于2022年，星期五例题v例例题1货币兑换（pku186

28、0|zju1544）v若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率，货币A到货币B的汇率表示要多少单位的货币B才能兑换到一个单位的货币A。当然货币兑换要支付一定量的中转费。v例如，如果你想将100美元兑换成俄元，汇率是29.75，中转费为0.39，v那么你会兑换到(100-0.39)29.75=2963.3975俄元。Company Logo第49页，共57页，编辑于2022年，星期五例题v城市中流通着N(N=100)类货币，用数字1至N标号表示。每个货币兑换点用6个数字来描述：整数A和B是兑换货币的编

29、号，实数RAB，CAB，RBA，CBA分别是A兑换成B和B兑换成A的汇率和中转费用。vNick有一些第S类货币，他想在若干次交换后增加他的资金，当然这些资金最终仍是第S类货币。请你告诉他该想法能否实现vSampleInput32120.0/货币数量,兑换点数量,初始货币编号资金121.001.001.001.00/A,B,Rab,Rba,Cab,Cba231.101.001.101.00SampleOutputYESCompany Logo第50页，共57页，编辑于2022年，星期五分析v如果我们可以求出，通过一系列的兑换每种货币可以得到的最大值，那么问题便迎刃而解了。v因为要是可以得到的第S

30、类货币最大值都不比初值大，资金肯定无法增加；否则，得到最大值的过程就是一种解法。v到了这里，我们发现求最大值和我们学过的求最短路很类似，构图用最短路算法做也显得水到渠成了。v具体做法是：v将N种货币看成N个结点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A货币兑换到B货币的汇率和中转费用为RAB，CAB，那么由对应的A结点向B结点连一条有向边，从A点得到的B的可能最大值为：(A目前的最大值-CAB)RAB。Company Logo第51页，共57页，编辑于2022年，星期五分析v注意，这里所求的是最大值，为了转化为最短路，我们可以在数字前面加上一个负号。v更简洁的方法是利用求最短路的方

31、法，求最长路。v由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，我们可以用Bellman-Ford算法或者SPFA算法做，这里用Bellman-Ford就够了。v需要指出一点，无论是求负权最短路还是求最长路，可能遇到的一个问题是：存在环，从而导致货币最大值不存在（因为可以沿环使最大值不断增大）。Company Logo第52页，共57页，编辑于2022年，星期五最短路算法总结vDijkstra算法的效率高，但是也有局限性，就是对于含负权的图无能为力。vBellman-Ford算法对于所有最短路长存在的图都适用，但是效率常常不尽人意。vSPFA算法可以说是综合了上述两

32、者的优点。它的效率同样很不错，而且对于最短路长存在的图都适用，无论是否存在负权。它的编程复杂度也很低，是性价比极高的算法。v对于绝大多数最短路问题，我们只需套用经典算法就行了。所以往往我们的难点是在模型的建立上。Company Logo第53页，共57页，编辑于2022年，星期五二分图匹配问题v二分图是指这样的图：图的顶点分成X和Y的集合，同一集合的顶点不存在边相连，只有不同集合的顶点才有可能有边直接相连。v二分图的一个匹配是指求出一个边的集合，使得集合里任意两条边都没有公共的顶点。也就是说一个顶点最多只可能属于一条边。v二分图的最大匹配就是找出边数最大的一个边集，也就是求最多有多少对顶点可以

33、被匹配上。v二分图最大匹配有着比较广泛的应用背景，例如一群工人可以做一堆工作，但是每个人只能做一份，如何合理安排工人们使得可以完成最多份的工作。v二分图最大匹配可以用网络流或是匈牙利算法Company Logo第54页，共57页，编辑于2022年，星期五二分图的一个例子v假如让你当月下老人，你知道现在有n对男女。v你知道他们之间谁和谁互相有爱意。v问你如何牵红线使得最多对的男女结合在一起。Company Logo第55页，共57页，编辑于2022年，星期五总结v“模型”一词曾在无数论文中被提及，它是图论基本思想的精华，是解决图论问题的关键。建立模型要求我们熟悉经典模型，同时又要求我们能够勇于探索，大胆创新，敢于跳出经典模型的框框。利用模型的特性需要我们独具慧眼，能够抓住问题的本质，击中问题的要害。v希望本节课对大家有一定的启发，使大家能够对图论基本算法及方法进行深入思考和总结。所谓万变不离其宗，只有最基本的思想和方法才是解决问题的不二法门。Company Logo第56页，共57页，编辑于2022年，星期五QQ:22007637QQ:22007637第57页，共57页，编辑于2022年，星期五