图的连通性总结.doc

图的连通性总结 boboo目录1. 图的遍历及应用1.1. DFS遍历1.2. DFS树的边分类1.3. DFS树的性质1.4. 拓补排序1.5. 欧拉回路2. 无向图相关2.1 求割顶2.2 求图的桥2.3 求图的块3. 有向图相关3.1 求强连通分量（SCC划分）3.2 求传递闭包4. 最小环问题一、图的遍历及应用1.1 DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。DFS对图进行染色，白色：未访问；灰色：访问中（正在访问它的后代）；黑色：访问完毕一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。-发现时间Dv:变灰的时间-结束时间fv:变黑的时间-1=dvfv=2|V|伪代码：DFS(G) for every vertex u VG do coloru = WHITEu = NIL time = 0for every vertex u VG doif coloru = WHITE then DFS_VISIT(u)DFS_VISIT(u)coloru = GRAY du = time += 1for every vertex v Adju doif colorv = WHITE thenv = uDFS_VISIT(v)coloru = BLACKfu = time += 11.2 DFS树的边分类在深度优先遍历中，我们所关心的另一个问题是对产生的搜索树中的分进行分类，这种分类可以发现图中的很多重要信息。一般地，我们可以把图G所产生的深度优先搜索树（或森林）的边分为四类：A）树枝：深度优先搜索树G中普通的边，即如果结点v在搜索边(u, v)时第一次被发现，那么边(u, v)就是一个树枝。B）反向边：深度优先搜索树中连结结点u到它的祖先v的那些边，自环也被认为是反向边。C）正向边：深度优先搜索树中连接顶点u到它的后裔的非树枝的边。D）交叉边：所有其它类型的边，它们可以连结同一棵深度优先搜索树中的两个结点，只要一结点不是另一结点的祖先（一般来讲两个结点是一种兄弟关系），也可以连结分属两棵深度优先搜索树的结点。我们可以把DFS遍历算法做一下补允，使之遇到边时能对其进行分类。算法的核心思想在于可以根据第一次被搜索的边所达到的结点v的颜色来对该边(u, v)进行分类（但正向边和交叉分不能用颜色区分出）。1、白色表明它是树枝。2、灰色表明它是反向边。3、黑色表明它是正向边或交叉边，其中，如果du dv，则(u, v)就是交叉边。上述证明比较简单，可根据定义证明。另外，如果图G为无向图的话，那么G的深度优先搜索树中的边只能是树枝或反向边。 在程序具体使显示颜色值以及时间戳可以省略, 用意义更加明确的pre数组和post代替d和f数组, preu和postu代表点u的先序/后序编号, 则检查(u,v)可以写为if (prev = -1) then dfs(v) /树边, 递归遍历else if (postv = -1) then show(“B”) /后向边else if (prev preu) then show(“F”) / 前向边else show(“C”); / 交叉边 pre和post的初值均为-1(0), 方便了判断程序实现： 1.3 DFS树的性质 括号结构性质对于任意结点对(u, v), 考虑区间du, fu和dv, fv, 以下三个性质恰有一个成立: 完全分离 u的区间完全包含在v的区间内, 则在dfs树上u是v的后代 v的区间完全包含在u的区间内, 则在dfs树上v是u的后代 定理1(嵌套区间定理): 在DFS森林中v是u的后代当且仅当dudvfv= dPu, 则它的父亲v=Pu是割点。程序实现2.2 求图的桥桥（割边）是去掉后让无向图不再连通的边。 求割边的算法也在DFS遍历的算法上形成。 什么样的边是桥（割边）？边(u,v)为桥当且仅当它不在任何一个简单回路中。发现树边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的后向边, 则删除(u,v)后u和v不连通, 因此(u,v)为桥。 桥（割边）的判定算法：发现树边(u, v)时若Lowlinkvdu(注意不能取等号,区别于求割顶), 则(u,v)为桥实际代码是测试若lowlinkv=prev则(u,v)是桥程序实现2.3 求图的块 一些连通性的基本定义：点连通度(等价性: Whitney定理)定义1: 把图变非连通所需删除的最少点数1-连通: 一般连通2-连通: 双连通, 删除一个点后仍连通(无割顶)定义2: 任意两个点至少有k个不含相同结点的路(vertex-disjoint path). 边连通度(等价性: Menger定理)定义1: 把图变非连通所需删除的最小边数定义2: 任意两个点至少有k个不含相同边的路(edge-disjoint path).块的定义以及性质：一个图的块(biconnectedcomponent, bcc)是双连通的极大子图。块与块之间没有公共边，以割顶相连。性质1. 每条边都包含在某个BCC中. 证明: 对于(u, v), u, v是双连通的, 这是某BCC的一部分性质2. 不同的两个BCC最多有一个公共结点, 此结点是原图的割顶性质3. 不同的两个BCC不含公共边. 证明: 如果有相同边, 则含有两个公共结点.根据性质2和性质3可知: BCC是G的边划分块可以表示成点或边的集合。一个显而易见的算法：先求出所有的割顶，去掉后，对不是割顶的点进行种子染色法（此时要把割顶当成不能再扩展的边界），这样就可以得到所有的块了。有没有更快更直接的方法呢？有！求块的算法：w 在求割点的算法中，我们找到割点u时，我们把u下方的整块和u导出作为图中的一个块。w 程序实现时用栈即可。程序实现：（用 floodfill） （用栈）三、有向图相关3.1求强连通分量（SCC划分）在有向图中，如果结点u可达到结点v，并不意味着结点v也可达到结点u，如果两个结点相互可达，那么称这两个结点处于同一个强连通分量（Strongly Connected Component, SCC）。SCC有一个比较有趣的性质，即：图G的SCC与G的转制GT的SCC相同。如果把SCC的每个分量都收缩成一个点，那么，生成的图为一个DAG。有关求有向图SCC划分的算法有很多，其中各有特点，也都比较优美，效率都还不错，实现起来也比较简单，同时，SCC划分也是有向图一个很基本但重要的算法，要熟练掌握，这里记录三种算法。 Kosaraju算法这个算法是一个应用了SCC图转制的性质与拓扑排序的一些思想的算法，整体算法非常之优美，是一个精美的算法，同时实现起来也非常简单，思想也不难理解。这里就直接给出整体思想，具体证明目前先从略，待以后补上。Kosaraju-SCC(G)1、调用DFS(G)以计算出每个结点的完成时刻fu； 2、计算出GT； 3、调用DFS(GT)，但在DFS的主循环按fu递减的顺序访问各结点； 4、输出3中产生的深度优先森林中每棵树的结点，作为各自独立的SCC。这个算法需要做两次DFS，而且需要做一个图的转制，时间复杂度为：O(V+E)。虽然这个复杂度渐进意义上是不错的，但是其中的常数较高，效率较其它的求SCC划分的算法稍差。 Tarjan算法这个算法是建立在图的DFS遍历基础上的。首先，它对每个图G中的点v定义了一个low函数（这个函数比较重要，在求图的割顶与桥等多种算法中也要用到），定义如下：定义这个函数以后，我们就可以得如出下性质：处于同一强连通分量里的点u与v的low函数值相同。根据这个性质，对DFS算法改进一下后，求出每个点的low函数值，进而也就可以求出图的强连通分量了，伪代码如下：Tarjan-SCC(G)for every vertex u VG docoloru = WHITEtime = 0for every vertex u VG doif coloru = WHITE then VISIT(u)VISIT(u)min = lowu = time += 1coloru = GRAYfor every vertex v Adju doif colorv = WHITE thenvisit(v)else if (colorv = GRAY) and (lowv min) thenmin = lowvif min lowu then lowu = mincoloru = BLACK很显然，算法的时间复杂度为：O(V+E)，整个算法只执行一遍DFS遍历，相对比Kosaraju算法效率稍高，整体实现起来也很简单，可以做为一个实用的求图SCC划分的算法。 Gabow算法 Gabow算法使用另一个栈P保留当前路径中的结点, 发现反向边(u,v)后不断出栈, 只保留v程序实现：（输出的都是最大的强连通分量中的点个数） 3.2 求传递闭包对于图G的任意一个结点u, u可达的结点集合称为u的传递闭包一个简单快捷的方法：用Floyd，再枚举判断。时间复杂度：O（n3）.更快更好的方法：区别对待有向图与无向图：无向图: u的传递闭包为和u处于同一连通分量的点集，floodfill即可有向图: 先求SCC图, 则u的传递闭包为u所处SCC和它的所有后代SCC中的结点，因此对于有向图只需在SCC划分的程序基础上完成即可。具体操作时：建立起SCC划分后的新图，新图是一棵树，从此点所属的SCC拓展即可，它及每个后代SCC中的所有点即为这个点的传递闭包。程序实现： 有向图的情况，且用的是tarjan算法。四、最小环问题简要介绍它的两种算法：1. 删边求最短路，每条边都要求一次，最短路可用dijkstra 或