《图论相关算法ppt课件.ppt》由会员分享，可在线阅读，更多相关《图论相关算法ppt课件.ppt（125页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图论相关算法图论相关算法图的组织形式l点、边（有向、无向）、权（容量、费用）l矩阵、邻接表广度优先搜索l通常用队列(先进先出,FIFO)实现Q=起点s; 标记s为己访问;while (Q非空) 取Q队首元素u; u出队;所有与u相邻且未被访问的点进入队列;标记u为已访问;广度优先搜索l由BFS得到的路径是原图中从S到T的边数最少的路径l广度优先搜索树不唯一广度优先搜索l双向广度优先搜索适用于已知出发点和结束点的BFS减少不必要的状态，搜索加速分析：搜索分支因子为r（每次可扩展状态数），需要k层，总状态数为rk，双向，前后各rk/2，总状态数2 rk/2哈希判重广度优先搜索l无向图的连通分量无向
2、图的连通分量是指，在连通分量里面的任意两个点之间都有路。易知从某个点v开始进行一次BFS，遍历到的所有点和v就在同一个连通分量内。广度优先搜索l例题：无向单位边权值图，300000个点，编号1n，列出所有中心点的编号中心点：到图中其他所有点的最长距离最小的点广度优先搜索l解法：广搜，遍历原图，生成BFS树求树的直径，即树的最长路直径的中间节点（1个或者2个）为中心点广度优先搜索l树的直径求法：选任意点开始BFS选BFS中深度最大的一个点为直径的一个端点从该端点出发再BFS最深的节点为另一端点，且深度为直径长度深度优先搜索l相关概念递归实现结点颜色：l白色（开始），灰色（发现），黑色（结束） 一
3、个结点总是从白色变为灰色，再变为黑色当所有点都变为黑色时，遍历结束时间戳(timestamp): du表示一个结点开始被访问的时间，fu表示一个结点结束访问的时间深度优先搜索int timestamp = 0;dfs(int p) timestamp = timestamp + 1;colp = GREY;dp = timestamp;for (每个与p相邻的点i)if (coli = WHITE) dfs(i);timestamp = timestamp + 1;fp = timestamp;colp = BLACK;深度优先搜索l每个顶点的du fulDFS中，v是u的子孙 dudvfv=
4、2）的标号的GCD为1深度优先搜索l割点与割边如果从图中删去某点和与该点相关联的边后，图不再连通，那么这个点叫做割点(cut point)。如果从图中删去某条边后，图不再连通，那么这条边叫做割边或桥(bridge)。深度优先搜索l思路depu记录节点u在DFS树中的深度lowu记录节点u的子孙所能达到的最浅深度u为割点lu为根，且有大于1个儿子lu不为根，且u的某个儿子v有lowv = depu(u,v)为割边l点u的某个儿子v，有lowv depu深度优先搜索dfs(int k,int father, int depth) colk = GREY; depk = depth; tot = 0
5、;for (每个与k相邻的点i) if (i != father & coli = GREY)lowk = min(lowk, depi);if (coli = WHITE) dfs(i, k, depth+1);tot = tot + 1;lowk = min(lowk, lowi);if (k为根 & tot1)|(k不为根 & lowi = depk)k为割点;if (lowi depk) then (k,i)为割边;colk = BLACK;深度优先搜索l例题：某公司拥有N台计算机，并将他们组成局域网，现在要求寻找该局域网中的关键点（即割点），并求出一旦处于该关键点的计算机崩溃，原局域
6、网将会分成多少个子网深度优先搜索lSample Input1 2 5 4 3 1 3 2 3 4 3 5 01 2 2 3 3 4 4 5 5 1 0 1 2 2 3 3 4 4 6 6 3 2 5 5 1 0深度优先搜索lSample OutputNetwork #1 : lSPF node 3 leaves 2 subnetsNetwork #2 : lNo SPF nodes Network #3 : lSPF node 2 leaves 2 subnets lSPF node 3 leaves 2 subnets 深度优先搜索l解法：求割点，计算删除该点使连通分量增加数对于DFS森林，
7、对每个割点记录一个cnt值，若有一个儿子v使得lowv = depu则使cntu+，则有如下性质：l对每个非根割点，删除该节点会增加cntu个连通分量l对每个根割点，删除该点会使图的连通分量增加其儿子数-1个拓扑排序l图的结点存在一个拓扑序：如果图中有边(u，v)，则u必定排在v的前面l拓扑排序在有向无环图(DAG)上进行l拓扑序列不一定唯一拓扑排序l利用DFS，当节点u已经扩展完成，将标记颜色置为黑时，将u加入已排序列的顶部，搜索完成时，节点序列为拓扑序l经过拓扑排序的顶点以与其完成时刻相反的顺序出现拓扑排序l算法(1) 计算每个点的入度，入度为0的点加入队列Q(2) 从Q中取出一个点p，输
8、出(3) 所有与p相邻的点的入度减1。如果新得到了入度为0的点，则加入队列Q。(4) 转步骤(2), 直到所有点都输出完毕如果在执行过程中发现找不到入度为0的点, 说明图中存在环拓扑排序l1 3 2 4 5 6 7 8 (不唯一)l如何生成最小字典序的拓扑序列？可以使用最小堆维护当前入度为0的节点21348756强连通分量l有向图的强连通分量（SCC）指：对于强连通分量里面的任意两个节点u和v，都存在u到v和v到u的路强连通分量l思路：对原图G进行DFS，记录各点的结束时间，把原图G的所有边反向为GT，在GT以各点结束时间递减的顺序DFS，则每棵树都是一个强连通分量即第一遍DFS生成拓扑序，以
9、拓扑序做第二次DFS强连通分量l缩点操作生成一个新的有向图Gscc，将每个强连通分量作为新图的一个点，原图连通分量内部的边删除，连通分量之间的边保留新图必定有拓扑序，即不会出现有向环(DAG)Gscc称为原图的核心DAG强连通分量强连通分量l例题：队长要向所有人通知某件事情，因为人数众多，他想出了一个省力的方法：他只通知队中的某些人，然后让这些人去通知所有他们认识的人，这些新被通知的人又去通知更多的人直到最后队中的所有人都被通知到。给定队长通知每个人所需的花费，现在他想求出一种方案，使得花费最少，并且保证最终所有人都能被通知到。强连通分量lSample Input4 3 30 20 10 40
10、 1 2 2 12 3 lSample Output60 强连通分量l解题：同一个强连通分量里，只要有一人被通知即可缩点后得到的DAG中，如果一个点被通知，则它的所有后继结点都会被通知。故只需通知入度为0的点在入度为0的每个点所表示的连通分量中，通知花费最少的那个人，即为最优解强连通分量l例题：给一个有向图G，添加最少的边数使得G中各点能两两互通（即每对点a和b，a能到b，b也能到a），求最少的边数强连通分量l解题：对原图求强连通分量，形成新的DAG图Gscc对Gscc计算入度为0的点的个数为x对Gscc计算出度为0的点的个数为y答案为max (x, y)，即从出度为0的点向入度为0的点连ma
11、x (x, y)条边欧拉路l欧拉路：经过图中每条边恰好一次的路l欧拉回路：起点和终点相同的欧拉路欧拉路l无向图存在欧拉路的条件如果图连通，且所有的点都是偶数度，则有欧拉回路。如果图连通，且恰有两点是奇数度，则有欧拉路。且欧拉路的起止点为这两个奇数度点。对重边、自环的情况仍适用。欧拉路l有向图存在欧拉路的条件如果图连通，且每个点的入度等于出度，则存在欧拉回路。如果图连通，且恰有一点u的出度比入度大1，另有一点v的出度比入度小1，其余的出度等于出度，则存在欧拉路，起点为u，终点为v。对重边、自环的情况仍适用。欧拉路l 套圈算法void Euler(int start) for (int i = 1
12、; i = E; i +) if (!visiti & from = start) visiti = 1;Euler(to);path+ top = i; l 倒序path为欧拉路欧拉路l例题：给定一组单词，问这些单词能否连成一串，使得前面一个单词的最后一个字母和后面一个单词的第一个字母相同。欧拉路l Sample Input 6 aloha arachnid dog gopher rat tiger 3 oak maple elm l Sample Outputaloha.arachnid.dog.gopher.rat.tiger * 欧拉路l解法：先判断连通性每个单词相当于在首字母和尾字母
13、之间连一条边得到一个最多26个点的有向图求欧拉路汉密尔顿路l汉密尔顿路：经过图中每个点恰好一次的路l汉密尔顿回路：起点和终点相同的汉密尔顿路l常见方法：状态压缩DP 汉密尔顿路l对于点数较少的情况，可以用状态压缩的DP来做。比如用optmaskk表示已经访问过mask表示的结点集合，并且最后位于点k的最优解。l状态转移方程为：optmaskk = min(optmask-ki + costik)i是所有与k相邻的点，mask-k指从mask除去k最短路径l单源最短路径DijkstraBellman-FordSPFAl任意两点间Floyd最短路径l复杂度：Dijkstra: O(V2)或O(E+
14、VlgV)Bellman-Ford: O(EV)Floyd: O(V3)SPFA: 期望复杂度O(E)最短路径l算法选择：编程复杂度：Bellman-FordFloydDijkstra时间复杂度：Dijkstra di + costij) dj = di + costij;最短路径lDijkstra最短路径lBellman-Ford主体思想：l对图中每条边做|V| - 1次松弛操作，即可确定最短路径，当有负权值时，再对所有边做一次松弛操作，若dis值仍有变化则表明存在负环最短路径lbool Bellman(int n , int m)l/*bellman , return false when
15、 there is a nagetive circle*/lint u , v , w , i , j;lbool flag ;lfor(i = 1 ; i = n ; i +) lflag = 0;lfor(j = 0 ; j disu + w) ldisv = disu + w;lflag = 1;lllif(!flag) break;lif(i = n & flag)return false;llreturn true;l最短路径lSPFA作为一种动态逼近的方法，是一种迭代模式，不仅仅可以用在最短路中，可以解决带环的DP问题最短路径Q=s; ds = 0;while (Q非空) 取队首元
16、素u; u出队;for (与u相邻的点v) if (dv du + costuv) dv = du + costuv;if (v不在队中) then v入队;/若某个点入队次数达到|v|说明有负环l 可以用循环队列实现，队列中元素个数不超过|V|最短路径l例题：最小平均环路图的每条边有两个权值a和b，在图上找一个环，使得对于环上的所有边（a/ b）最小最短路径l解法：二分答案设答案为k，使各边的边权值为kbi ai，在新图中用Bellman-Ford或者SPFA判断是否含有负环若有负环，则kbi ai 0 即 k a/ b，即可再扩大k最短路径l例题：有向图，N个节点编号1N，M条边，权值均为
17、正，现给定k个可替换条件，可以将M条件中的k条边权值替换为0，求在至多替换k条边的情况下，节点1到节点N的最短路径最短路径l解法：多层图建立一个多层图，有k+1层，每层都为原图，只有相邻层之间可建边，且相邻层间只能建立由低层到高层的边，若图中有边（i，j）权值为p，则建立下层节点i到上层节点j的权值为0的边第0层（最下一层）节点1到第k层（最上一层）节点N的最短路径为所求差分约束l差分约束系统是一组形如 x-y=C 的不等式x1 x2 = 0 x1 x5 = -1x2 x5 = 1x3 x1 = 5x4 x1 = 4x4 x3 = -1x5 x3 = -3x5 x4 du + cost)the
18、n dv = du + cost;在最短路算法执行完毕后，对所有的边(u,v)都有dv = du + cost变形得dv du = cost ;容易看出，上式即为差分约束系统的标准形式。差分约束l解不等式组问题转化为图论问题：不等式组中的每个变量作为图中的一个点对于每个不等式Xi Xj ，=，=l当某些点有明显的=性质时，可以计算和值，使得Si Si-1产生=形式，构造求解l实际问题中有些不等关系较隐蔽，注意不要遗漏l如果把所有的Xi同时加一个值，不等式组仍然成立生成树l最小生成树：Prim (O(ElogV)Kruskal (O(ElogE)+O(alpha*E)l算法的选择：从图的稀疏程度
19、考虑从问题对边的限制考虑最小生成树lPrim算法：(1) 任意选定一点s，设集合S=s(2) 从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则(i，j)就是生成树上的一条边，同时将j点加入S(3) 转到(2)继续进行，直至所有点都己加入S集合。最小生成树50461321025142422161850461210251422161231228最小生成树lKruskal算法：将边按权值从小到大排序后逐个判断，如果当前的边加入以后不会产生环，那么就把当前边作为生成树的一条边。最终得到的结果就是最小生成树。并查集最小生成树50461321025142416181250461321025
20、141222222816生成树l其他生成树问题：最小树形图l有向图的最小生成树次小生成树l假设T为G的最小生成树集合，并设T为T的最小生成树，那么次小生成树是集合T-T 中权值最小的生成树生成树l其他生成树问题：最小度限制生成树l对于一个加权的无向图，存在一些满足下面性质的生成树：某个特殊的结点的度等于一个指定的数值。最小度限制生成树就是满足此性质且权值和最小的一棵生成树最优比率生成树l已知一个完全图，每条边有两个参数（dis和c），求一棵生成树，使(xici)/(xidisi)最小，其中xi当第i条边包含在生成树中时为1，否则为0 二分图l所有点可以分成两个集合X和Y，使得所有的边的一端在X
21、集合，另一端在Y集合l二分图的充要条件：图中不含奇环l二分图的判定：用BFS或DFS对点进行黑白染色，检查是否出现矛盾二分图最大匹配l二分图的最大匹配指找到尽可能多的边，使得它们之间没有相同的端点二分图最大匹配l交错路对于一个匹配M，如果能找到一条奇数长度的路，使得路的第一、三、五边不属于M，而第二、四、六边属于M，那么这条路叫做交错路。交错路可以“增广”，即通过适当修改得到更长的路。一个匹配是最大匹配当且仅当不能再找到交错链为止二分图最大匹配l交错路增广示例 (1-2-3-4-5-6-7-8)12345678二分图最大匹配l匈牙利算法一个匹配为最大匹配匹配中不存在交错路利用BFS或者DFS实
22、现寻找交错路以每个节点为起点找一次增广路即可求得最大匹配，寻找增广路的复杂度为O（E），总的复杂度为O（VE）二分图最大匹配l bool Bipartite_Dfs(int u) lfor(int i = 0 ; i adju.size() ; i +) lif(!markadjui) lmarkadjui = 1;lint t = matchadjui;lmatchadjui = u;lif(!t | Bipartite_Dfs(t)return true;lmatchadjui = t;lllreturn false;l l -l Clear(match);l for(i = 1 ; i
23、= n ; i +) lClear(mark);lif(Bipartite_Dfs(i)ans +;l 二分图最大匹配l可以在调用DFS增广之前利用贪心的策略做初始的基本匹配，若贪心解接近最终解则可提高效率l常见模型：非攻击车：行列分为两部分，允许放车的格子连边骨牌覆盖：染色，相邻黑白格连边二分图最大匹配l例题：给一个NM的格子，其中X表示不能走，E表示出口，.表示有一个人。所有人只能上下左右行走，且所有人都要选择一个出口走出去，但每个时刻每个出口只能走出去一个人，问是否所有人都能出去，如果是，求都能出去的最小时间二分图最大匹配l解答：二分答案+最大匹配验证从每个E出口BFS遍历每个.人，计算
24、编号为i的人到编号为j的出口的最短距离（也是最短时间），记录于cntij二分最后时间k，将原总共d个出口拆成kd个出口，若cntij |cari.c - carj.a| + |cari.d - carj.b| l则建立i到j的边答案 = 顶点数 最大匹配数二分图最优匹配l二分图最优匹配（带权最大匹配）：二分图的每条边上带有权值，求一个匹配使得匹配边上的权值和最大。l实际问题：每个工人操作不同机器的效率不同，如何合理分配机器，使得效率总和达到最佳？每对男女之间的好感度不同，如何配对使得总的好感度最高？二分图最优匹配lKM算法：基本概念：可行顶标与相等子图可行顶标是一个关于节点的函数L且对于每条边
25、(x，y)满足L(x) + L(y) = w(x,y)相等子图是指只包含L(x) + L(y) = w(x,y)的边的子图。定理：如果相等子图有完备匹配（包含所有点的匹配），则该匹配是最大权匹配。二分图最优匹配lKM算法的关键：通过适当地修改可行顶标从而使相等子图有完备匹配，于是就可以得到最优匹配。l设顶点Xi的顶标为ai，顶点Yi的顶标为bi。初始时，ai为与Xi相关联的边的最大权值，bj=0，保证ai+bj=w(i,j)成立。二分图最优匹配l若相等子图中不包含完备匹配时，就适当修改顶标以扩大相等子图，直到找到完备匹配为止l当从Xi寻找交错路失败后，得到一棵交错树，它的所有叶子节点都是X节点
26、，取所有左侧点i在树中而右侧j不在树中的边(i,j)，计算d=minai+bj-wij。交错树中所有左侧点顶标-d，右侧点顶标+d二分图最优匹配l 对于图中所有的边(i,j)，可以看到 若i和j都不在交错树中，边(i,j)仍不属于相等子图 若i和j都在交错树中，边(i,j)仍然属于相等子图 若i在交错树中，j不在交错树中，ai+bj减少，边(i,j)有可能加入到相等子图中l 每次更新顶标，至少有一条边新加入相等子图，匹配也就可能继续扩大二分图最优匹配l例题：在一片花园中，有人（H），有屋（m），有空地（.），且人和屋子的数量一致，每个屋子只能住一个人，每个人只能上下左右四个方向行走，现在给你花
27、园的现状，求使每个人都能进到屋子里的最小步数二分图最优匹配l Sample Input 5 5 HH.m . . . mm.H 7 8 .H. .H. .H. mmmHmmmm .H. .H. .H.l Sample Output 10 28 二分图最优匹配l解法：初始算出每个人到每个房子所需要的步数，X集为N个人，Y集为N个房子，若人i到房子j需要步数为c，则人i和房子j之间连边，权值为-c由于房子数和人数一致，可以使用KM算法求解求出的结果值再取负即为答案二分图最优匹配l注意在使用KM算法时需要注意X集和Y集的节点数是否一致，否则需要补点补边算最大值时可以令边权为正，反之算最小值时可以令边
28、权为负，最后结果再取负网络流l网络流基本概念：源点(source, 常记为s)汇点(sink, 常记为t)容量(capacity, 常用c(x,y)表示)流(flow, 常用f(x,y)表示)网络流l容量限制条件：对于所有边，有f(x,y)出度的点u，连边（u，t）容量为x；对于出度入度的点v，连边（s，v）容量为x若有满流，将流量非0的边反向则可得到欧拉回路最大权闭合子图l闭合图：有向图的一个点集，该点集的所有出边仍指向该集l最大权闭合图：每个点一个权值，权值和最大的闭合图最大权闭合子图l建图：令点权为w，加入s和t，令所有原图中边的容量为无穷s连权值为正的点，容量为w；权值为负的点连t，容量为-w最大权闭合子图权值=所有正权值之和-最大流值最大权闭合子图l理解：对新图求最大流，相当于求最小割，原图中边容量为无穷，不会被割开，被割开的边相当于没选的正权点，和选中的负权点，减去最大流值即相当于取得最大权值图论其他知识l本课件中未涉及的知识点：中国邮路问题竞赛图的汉密尔顿路SAT问题最小费用流