图的连通性总结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对图进行染色，白色：未访问；灰色：访问中（正在访问它的后代）；黑色：访问完毕一般在具体实现时不必对图的顶点进行染色，只需进行访问开始时间和访问结束时间的记录即可，这样就可以得出需要的信息了。
-发现时间D[v]:变灰的时间-结束时间f[v]:变黑的时间-1<=d[v]<f[v]<=2|V|伪代码：DFS(G)for every vertex u ∈ V[G] docolor[u] = WHITEπ[u] = NILtime = 0for every vertex u ∈ V[G] doif color[u] = WHITE then DFS_VISIT(u)DFS_VISIT(u)color[u] = GRAYd[u] = time += 1for every vertex v ∈ Adj[u] doif color[v] = WHITE thenπ[v] = uDFS_VISIT(v)color[u] = BLACKf[u] = 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、黑色表明它是正向边或交叉边，其中，如果d[u] < d[v]，则边(u, v)就是正向边；反之，或d[u] > d[v]，则(u, v)就是交叉边。
上述证明比较简单，可根据定义证明。
另外，如果图G为无向图的话，那么G的深度优先搜索树中的边只能是树枝或反向边。
在程序具体使显示颜色值以及时间戳可以省略, 用意义更加明确的pre数组和post代替d 和f数组, pre[u]和post[u]代表点u的先序/后序编号, 则检查(u,v)可以写为if (pre[v] = -1) then dfs(v) //树边, 递归遍历else if (post[v] = -1) then show(“B”) //后向边else if (pre[v] > pre[u]) then show(“F”) // 前向边else show(“C”); // 交叉边• pre和post的初值均为-1(0), 方便了判断程序实现：1.3 DFS树的性质•括号结构性质对于任意结点对(u, v), 考虑区间[d[u], f[u]]和[d[v], f[v]], 以下三个性质恰有一个成立:–完全分离– u的区间完全包含在v的区间内, 则在dfs树上u是v的后代– v的区间完全包含在u的区间内, 则在dfs树上v是u的后代•定理1(嵌套区间定理):在DFS森林中v是u的后代当且仅当d[u]<d[v]<f[v]<f[u], 即区间包含关系. 由区间性质立即得到.•定理2(白色路径定理):在DFS森林中v是u的后代当且仅当在d[u]时刻(u刚刚被发现), v可以由u出发只经过白色结点到达. 证明: 由嵌套区间定理可以证明1.4 拓补排序算法一：•对图G使用DFS算法, 每次把一个结点变黑的同时加到链表首部•定理1: 有向图是DAG当且仅当没有B边–如果有B边, 有环(易证)–如果有环c, 考虑其中第一个被发现的结点v, 环中v的上一个结点为u, 则沿环的路径v u是白色路径, 有白色路径定理, u是v的后代, 因此(u,v)是B边•定理2: 该算法正确的得到了一个拓扑顺序算法二：其实还有更方便的方法，不必进行dfs遍历，统计入度的情况即可。
程序实现：(这里只给出DFS的方法)1.5 欧拉回路每条边经过一次且仅一次的路径。
经典的递归实现.算法：从一个点u出发DFS，每次标记边(u,v)和(v,u)，递归调用EulerRoute(v)，然后把(u,v)放到栈中.程序实现：二、无向图相关2.1 求割顶割顶是去掉后让无向图不再连通的点。
求割顶的算法在DFS遍历的算法上形成。
什么样的点是割顶？在一棵DFS树中，1.根root是割顶 ------------- 它至少有两个儿子2.其他点v是割顶 ------------- 它有一个儿子u, 从u或者u的后代出发没有指向v祖先(不含v)的B边, 则删除v以后u和v的父亲不连通, 故为割顶。
割顶判定算法:引入lowlink数组为从当前点以及它的后代所能到达的点的开始访问时间的最小值。
Lowlink [u]= Min { pre[u]Pre[v] (u,v)是后向边Lowlink [v] (u，v）是树边，u在dfs树中是v的父亲 }–对于DFS树根, 判断度数是否大于1–对于其他点u, 如果不是根的直接儿子, 且Lowlink[u] >= d[P[u]], 则它的父亲v=P[u]是割点。
程序实现2.2 求图的桥桥（割边）是去掉后让无向图不再连通的边。
求割边的算法也在DFS遍历的算法上形成。
什么样的边是桥（割边）？边(u,v)为桥当且仅当它不在任何一个简单回路中。
发现树边(u,v)时若发现v和它的后代不存在一条连接u或其祖先的后向边, 则删除(u,v)后u和v不连通, 因此(u,v)为桥。
桥（割边）的判定算法：发现树边(u, v)时若Lowlink[v]>d[u](注意不能取等号,区别于求割顶), 则(u,v)为桥实际代码是测试若lowlink[v]=pre[v]则(u,v)是桥程序实现2.3 求图的块一些连通性的基本定义：•点连通度(等价性: Whitney定理)–定义1: 把图变非连通所需删除的最少点数•1-连通: 一般连通•2-连通: 双连通, 删除一个点后仍连通(无割顶)–定义1: 把图变非连通所需删除的最小边数–定义2: 任意两个点至少有k个不含相同边的路(edge-disjoint path).块的定义以及性质：一个图的块(biconnectedcomponent, bcc)是双连通的极大子图。
块与块之间没有公共边，以割顶相连。
•性质1. 每条边都包含在某个BCC中. 证明: 对于(u, v), {u, v}是双连通的, 这是某BCC的一部分•性质2. 不同的两个BCC最多有一个公共结点, 此结点是原图的割顶•性质3. 不同的两个BCC不含公共边. 证明: 如果有相同边, 则含有两个公共结点.•根据性质2和性质3可知: BCC是G的边划分块可以表示成点或边的集合。
一个显而易见的算法：先求出所有的割顶，去掉后，对不是割顶的点进行种子染色法（此时要把割顶当成不能再扩展的边界），这样就可以得到所有的块了。
有没有更快更直接的方法呢？有！求块的算法：♦在求割点的算法中，我们找到割点u时，我们把u下方的整块和u导出作为图中的一个块。
♦程序实现时用栈即可。
程序实现：（用floodfill）（用栈）三、有向图相关3.1求强连通分量（SCC划分）在有向图中，如果结点u 可达到结点v ，并不意味着结点v 也可达到结点u ，如果两个结点相互可达，那么称这两个结点处于同一个强连通分量（Strongly Connected Component, SCC ）。
SCC 有一个比较有趣的性质，即：图G 的SCC 与G 的转制G T 的SCC 相同。
如果把SCC 的每个分量都收缩成一个点，那么，生成的图为一个DAG 。
有关求有向图SCC 划分的算法有很多，其中各有特点，也都比较优美，效率都还不错，实现起来也比较简单，同时，SCC 划分也是有向图一个很基本但重要的算法，要熟练掌握，这里记录三种算法。
• Kosaraju 算法这个算法是一个应用了SCC 图转制的性质与拓扑排序的一些思想的算法，整体算法非常之优美，是一个精美的算法，同时实现起来也非常简单，思想也不难理解。
这里就直接给出整体思想，具体证明目前先从略，待以后补上。
Kosaraju-SCC(G)1、调用DFS(G)以计算出每个结点的完成时刻f[u]；2、计算出G T ；3、调用DFS(G T )，但在DFS 的主循环按f[u]递减的顺序访问各结点；4、输出3中产生的深度优先森林中每棵树的结点，作为各自独立的SCC 。
这个算法需要做两次DFS ，而且需要做一个图的转制，时间复杂度为：O (V +E )。
虽然这个复杂度渐进意义上是不错的，但是其中的常数较高，效率较其它的求SCC 划分的算法稍差。
• Tarjan 算法这个算法是建立在图的DFS 遍历基础上的。
首先，它对每个图G 中的点v 定义了一个low 函数（这个函数比较重要，在求图的割顶与桥等多种算法中也要用到），定义如下：()),(][][min ][w u u v w w d v d v low 所连的某条后向边的后裔为⎩⎨⎧=定义这个函数以后，我们就可以得如出下性质：处于同一强连通分量里的点u 与v 的low 函数值相同。
根据这个性质，对DFS 算法改进一下后，求出每个点的low 函数值，进而也就可以求出图的强连通分量了，伪代码如下：Tarjan-SCC(G)for every vertex u ∈ V[G] docolor[u] = WHITEtime = 0for every vertex u ∈ V[G] doif color[u] = WHITE then VISIT(u)VISIT(u)min = low[u] = time += 1color[u] = GRAYfor every vertex v ∈ Adj[u] doif color[v] = WHITE thenvisit(v)else if (color[v] = GRAY) and (low[v] < min) thenmin = low[v]if min < low[u] then low[u] = mincolor[u] = BLACK很显然，算法的时间复杂度为：O(V+E)，整个算法只执行一遍DFS遍历，相对比Kosaraju算法效率稍高，整体实现起来也很简单，可以做为一个实用的求图SCC划分的算法。