《图的基本算法》PPT课件.ppt

图的基本算法,CompanyLogo,图的一些基本概念及其表示,Contents,拓扑排序和欧拉回路问题,最小生成树和单源最短路问题,二分图匹配,1,2,3,4,CompanyLogo,定义与术语,图：二元组称为图(graph)。V为结点(node)点(vertex)集。E为中结点之间的边的集合。子图：什么是子图如果有两个图G和G，G的顶点集是G的顶点集的子集，且G的边集点对(u,v)称为边(edge)或称弧(arc)，其中u,v属于V，称u,v是相邻的(adjacent)，称u,v与边相关联(incident)。连通图：如果图中任意一对顶点都有路径存在，则称该图为连通的,CompanyLogo,定义与术语,若边的点对(u,v)有序则称为有向(directed)边，其中u称为头(head)，v称为尾(tail)。所形成的图称有向图(directedgraph)。为对于u来说是出边(outgoingarc)；对于v来说是入边(incomingarc)。反之，若边的点对无序则称为无向(undirected)边，所形成的图称无向图(undirectedgraph)。,CompanyLogo,定义与术语,度(degree):一个顶点的度是指与该边相关联的边的条数，顶点v的度记作deg(v)。无向图：有向图：入度(indegree):在有向图中，一个顶点v的入度是指与该边相关联的入边(即边的尾是v)的条数。出度(outdegree)：在有向图中，一个顶点的出度是指与该边相关联的出边(即边的头是v)的条数。路径：如果从一个顶点v1出发，沿着一些边依次经过一些定点v2,v3,vn,则称顶点序列(v1,v2,.,vn)为从顶点v1到vn的路径。回路：如果一条路径上第一个顶点和最后一个顶点是相同的，则称这样的路径为回路或环。,CompanyLogo,图的表示,要表示一个图G=(V,E),有两种标准的方法，即邻接表和邻接矩阵。这两种方法即可以用于有向图，也可以用于无向图。,用邻接表记录图,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赋给edgeu,CompanyLogo,遍历邻接表,for(inti=0;idestlink;/取链表的下一个元素,CompanyLogo,CompanyLogo,DFS，BFS拓扑排序强连通分支欧拉路径和回路最小生成树最短路径哈密顿回路(NP)差分约束系统网络流二分图匹配,图论涉及到的问题和算法,CompanyLogo,今天要讲的问题,最小生成树最短路算法,拓扑排序欧拉回路,二分图的匹配,拓扑排序,拓扑排序是对有向无回路图(DAG)顶点的一种排序，它使得如果存在u,v的有向路径，那么满足序中u在v前。拓扑排序就是由一种偏序(particalorder)得到一个全序(称为拓扑有序(topologicalorder)。偏序是满足自反性，反对称性，传递性的序。一个图的拓扑排序得到的结果可以看成是图中所有顶点沿水平线排列而成的序列，而且所有的有向边均是从左指向右在有向无回路图用于说明事件发生的先后顺序拓扑排序可以给出一个满足时间先后的顺序,CompanyLogo,陈熙大牛穿衣服的例子,CompanyLogo,拓扑排序算法描述,拓扑排序的思路很简单，就是每次任意找一个入度为0的点输出，并把这个点以及与这个点相关的边删除。实际算法中，用一个队列实现。算法：1.把所有入度=0的点入队Q。2.若队Q非空，则点u出队，输出u；否则转4。3.把所有与点u相关的边(u,v)删除，若此过程中有点v的入度变为0，则把v入队Q，转2。4.若出队点数N，则说明有圈。时间复杂度O(V+E),CompanyLogo,欧拉回路,欧拉回路，又称“一笔画”，是图论中可行遍性问题的一种欧拉回路问题是图论中最古老的问题之一。它诞生于十八世纪的欧洲古城哥尼斯堡。普瑞格尔河流经这座城市，人们在两岸以及河中间的两个小岛之间建了七座桥。市民们喜欢在这里散步，于是产生了这样一个问题：是否可以找到一种方案，使得人们从自己家里出发，不重复地走遍每一座桥，然后回到家中？这个问题如果用数学语言来描述，就是在右图中找出一条回路，使得它不重复地经过每一条边。这便是著名的“哥尼斯堡七桥问题”。,CompanyLogo,一些概念及定理,欧拉回路:图G中经过每条边一次并且仅一次的回路称作欧拉回路。欧拉路径:图G中经过每条边一次并且仅一次的路径称作欧拉路径。欧拉图:存在欧拉回路的图称为欧拉图。半欧拉图存在欧拉路径但不存在欧拉回路的图称为半欧拉图。我们经常需要判定一个图是否为欧拉图（或半欧拉图），并且找出一条欧拉回路（或欧拉路径）。对于无向图有如下结论：定理1无向图G为欧拉图，当且仅当G为连通图且所有顶点的度为偶数。,CompanyLogo,一些概念及定理,推论1无向图为半欧拉图，当且仅当G为连通图且除了两个顶点的度为奇数之外，其它所有顶点的度为偶数。定理2有向图为欧拉图，当且仅当G的基图连通，且所有顶点的入度等于出度。推论2有向图为半欧拉图，当且仅当G的基图连通，且存在顶点的入度比出度大1、的入度比出度小1，其它所有顶点的入度等于出度。基图：忽略有向图所有边的方向，得到的无向图称为该有向图的基图。,CompanyLogo,欧拉回路算法描述,由此可以得到以下求欧拉图的欧拉回路的算法：在图G中任意找一个回路；将图G中属于回路的边删除；在残留图的各极大连通子图中分别寻找欧拉回路；将各极大连通子图的欧拉回路合并到中得到图的欧拉回路。,CompanyLogo,算法描述,ProcedureEuler-circuit();BeginFor顶点start的每个邻接点vDoIf边(start,v)未被标记ThenBegin将边(start,v)作上标记;将边(v,start)作上标记;Euler-circuit(v);将边(start,v)加入栈;End;End;最后依次取出栈S每一条边而得到图G的欧拉回路。由于该算法执行过程中每条边最多访问两次，因此该算法的时间复杂度为O(E)。,CompanyLogo,例题,例题一单词游戏题目描述有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上面单词的末字母等于后一个盘子上面单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。数据规模Ndu+w(u,v)ThenReturnFALSEReturnTRUE时间复杂度为O(V*E);,CompanyLogo,执行过程,CompanyLogo,Bellman-Ford思想,Bellman-Ford算法的思想基于以下事实：“两点间如果有最短路，那么每个结点最多经过一次。也就是说，这条路不超过n-1条边。”（如果一个结点经过了两次，那么我们走了一个圈。如果这个圈的权为正，显然不划算；如果是负圈，那么最短路不存在；如果是零圈，去掉不影响最优值）根据最短路的最优子结构，路径边数上限为k时的最短路可以由边数上限为k-1时的最短路“加一条边”来求，而根据刚才的结论，最多只需要迭代n-1次就可以求出最短路。,CompanyLogo,SPFA,ShortestpathfasteralgorithmSPFA其实就是Bellman-Ford的一种队列实现，减少了冗余，即松驰的边至少不会以一个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（含有负圈）。,CompanyLogo,SPFA算法分析,一般用于找负圈(效率高于Bellman-Ford)，稀疏图的最短路由于点可能多次入队，但队列中同时不会超过n个点。所以用一个长度为n的循环队列来实现这个队。SPFA在形式上和宽度优先搜索非常类似，不同的是宽度优先搜索中一个点出了队列就不可能重新进入队列，但是SPFA中一个点可能在出队列之后再次被放入队列，也就是一个点改进过其它的点之后，过了一段时间可能本身被改进，于是再次用来改进其它的点，这样反复迭代下去。设一个点用来作为迭代点对其它点进行改进的平均次数为k，有办法证明对于通常的（不含负圈，较稀疏）情况，k在2左右。算法复杂度理论上同Bellman-Ford，O(nm)，但实际上却是O(km)。,CompanyLogo,例题,例题1货币兑换（pku1860|zju1544）若干个货币兑换点在我们的城市中工作着。每个兑换点只能进行两种指定货币的兑换。不同兑换点兑换的货币有可能相同。每个兑换点有它自己的兑换汇率，货币A到货币B的汇率表示要多少单位的货币B才能兑换到一个单位的货币A。当然货币兑换要支付一定量的中转费。例如，如果你想将100美元兑换成俄元，汇率是29.75，中转费为0.39，那么你会兑换到(100-0.39)29.75=2963.3975俄元。,CompanyLogo,例题,城市中流通着N(N=100)类货币，用数字1至N标号表示。每个货币兑换点用6个数字来描述：整数A和B是兑换货币的编号，实数RAB，CAB，RBA，CBA分别是A兑换成B和B兑换成A的汇率和中转费用。Nick有一些第S类货币，他想在若干次交换后增加他的资金，当然这些资金最终仍是第S类货币。请你告诉他该想法能否实现SampleInput32120.0/货币数量,兑换点数量,初始货币编号资金121.001.001.001.00/A,B,Rab,Rba,Cab,Cba231.101.001.101.00SampleOutputYES,CompanyLogo,分析,如果我们可以求出，通过一系列的兑换每种货币可以得到的最大值，那么问题便迎刃而解了。因为要是可以得到的第S类货币最大值都不比初值大，资金肯定无法增加；否则，得到最大值的过程就是一种解法。到了这里，我们发现求最大值和我们学过的求最短路很类似，构图用最短路算法做也显得水到渠成了。具体做法是：将N种货币看成N个结点，将每个兑换点转化为两条有向边。根据兑换公式，目前从A货币兑换到B货币的汇率和中转费用为RAB，CAB，那么由对应的A结点向B结点连一条有向边，从A点得到的B的可能最大值为：(A目前的最大值-CAB)RAB。,CompanyLogo,分析,注意，这里所求的是最大值，为了转化为最短路，我们可以在数字前面加上一个负号。更简洁的方法是利用求最短路的方法，求最长路。由于存在负权（求最长路和负权等价），所以在这里Dijkstra算法不适用了，我们可以用Bellman-Ford算法或者SPFA算法做，这里用Bellman-Ford就够了。需要指出一点，无论是求负权最短路还是求最长路，可能遇到的一个问题是：存在环，从而导致货币最大值不存在（因为可以沿环使最大值不断增大）。,CompanyLogo,最短路算法总结,Dijkstra算法的效率高，但是也有局限性，就是对于含负权的图无能为力。Bellman-Ford算法对于所有最短路长存在的图都适用，但是效率常常不尽人意。SPFA算法可以说是综合了上述两者的优点。它的效率同样很不错，而且对于最短路长存在的图都适用，无论是否存在负权。它的编程复杂度也很低，是性价比极高的算法。对于绝大多数最短路问题，我们只需套用经典算法就行了。所以往往我们的难点是在模型的建立上。,CompanyLogo,二分图匹配问题,二分图是指这样的图：图的顶点分成X和Y的集合，同一集合的顶点不存在边相连，只有不同集合的顶点才有可能有边直接相连。二分图的一个匹配是指求出一个边的集合，使得集合里任意两条边都没有公共的顶点。也就是说一个顶点最多只可能属于一条边。二分图的最大匹配就是找出边数最大的一个边集，也就是求最多有多少对顶点可以被匹配上。二分图最大匹配有着比较广泛的应用背景，例如一群工人可以做一堆工作，但是每个人只能做一份，如何合理安排工人们使得可以完成最多份的工作。二分图最大匹配可以用网络流或是匈牙利算法,CompanyLogo,二分图的一个例子,假如让你当月下老人，你知道现在有n对男女。你知道他们之