簡介： 割邊和割點的定義僅限於無向圖中。我們可以通過定義以蠻力方式求解出無向圖的所有割點和割邊,但這樣的求解方式效率低。Tarjan提出了一種快速求解的方式，通過一次DFS就求解出圖中所有的割點和割邊。 歡迎探討，如有錯誤敬請指正 如需轉載，請註明出處 http://www.cnblogs.com/ ...
簡介：
割邊和割點的定義僅限於無向圖中。我們可以通過定義以蠻力方式求解出無向圖的所有割點和割邊,但這樣的求解方式效率低。Tarjan提出了一種快速求解的方式，通過一次DFS就求解出圖中所有的割點和割邊。
歡迎探討，如有錯誤敬請指正
如需轉載，請註明出處 http://www.cnblogs.com/nullzx/
1. 割點與橋（割邊）的定義
在無向圖中才有割邊和割點的定義
割點：無向連通圖中，去掉一個頂點及和它相鄰的所有邊，圖中的連通分量數增加，則該頂點稱為割點。
橋（割邊）：無向聯通圖中，去掉一條邊，圖中的連通分量數增加，則這條邊，稱為橋或者割邊。
割點與橋（割邊）的關係：
1）有割點不一定有橋,有橋一定存在割點
2）橋一定是割點依附的邊。
下圖中頂點C為割點，但和C相連的邊都不是橋。
2. 暴力解決辦法解決求解割點集和割邊集
暴力法的原理就是通過定義求解割點和割邊。在圖中去掉某個頂點，然後進行DFS遍歷，如果連通分量增加，那麼該頂點就是割點。如果在圖中去掉某條邊，然後進行DFS遍歷，如果連通分量增加，那麼該邊就是割邊。對每個頂點或者每個邊進行一次上述操作，就可以求出這個圖的所有割點和割邊，我們稱之為這個圖的割點集和割邊集。
在具體的代碼實現中，並不需要真正刪除該頂點和刪除依附於該頂點所有邊。對於割點，我們只需要在DFS前，將該頂點對應是否已訪問的標記置為ture，然後從其它頂點為根進行DFS即可。對於割邊，我們只需要禁止從這條邊進行DFS後，如果聯通分量增加了，那麼這條邊就是割邊。
3. Tarjan演算法的原理
判斷一個頂點是不是割點除了從定義，還可以從DFS（深度優先遍歷）的角度出發。我們先通過DFS定義兩個概念。
假設DFS中我們從頂點U訪問到了頂點V（此時頂點V還未被訪問過），那麼我們稱頂點U為頂點V的父頂點，V為U的孩子頂點。在頂點U之前被訪問過的頂點，我們就稱之為U的祖先頂點。
顯然如果頂點U的所有孩子頂點可以不通過父頂點U而訪問到U的祖先頂點，那麼說明此時去掉頂點U不影響圖的連通性，U就不是割點。相反，如果頂點U至少存在一個孩子頂點，必須通過父頂點U才能訪問到U的祖先頂點，那麼去掉頂點U後，頂點U的祖先頂點和孩子頂點就不連通了，說明U是一個割點。
上圖中的箭頭表示DFS訪問的順序（而不表示有向圖），對於頂點D而言，D的孩子頂點可以通過連通區域1紅色的邊回到D的祖先頂點C（此時C已被訪問過），所以此時D不是割點。
上圖中的連通區域2中的頂點，必須通過D才能訪問到D的祖先頂點，所以說此時D為割點。再次強調一遍，箭頭僅僅表示DFS的訪問順序，而不是表示該圖是有向圖。
這裡我們還需要考慮一個特殊情況，就是DFS的根頂點（一般情況下是編號為0的頂點），因為根頂點沒有祖先頂點。其實根頂點是不是割點也很好判斷，如果從根頂點出發，一次DFS就能訪問到所有的頂點，那麼根頂點就不是割點。反之，如果回溯到根頂點後，還有未訪問過的頂點，需要在鄰接頂點上再次進行DFS，根頂點就是割點。
4. Tarjan演算法的實現細節
在具體實現Tarjan演算法上，我們需要在DFS（深度優先遍歷）中，額外定義三個數組dfn[]，low[]，parent[]
4.1 dfn數組
dnf數組的下標表示頂點的編號，數組中的值表示該頂點在DFS中的遍歷順序(或者說時間戳)，每訪問到一個未訪問過的頂點，訪問順序的值（時間戳）就增加1。子頂點的dfn值一定比父頂點的dfn值大（但不一定恰好大1，比如父頂點有兩個及兩個以上分支的情況）。在訪問一個頂點後，它的dfn的值就確定下來了，不會再改變。
4.2 low數組
low數組的下標表示頂點的編號，數組中的值表示DFS中該頂點不通過父頂點能訪問到的祖先頂點中最小的順序值（或者說時間戳）。
每個頂點初始的low值和dfn值應該一樣，在DFS中，我們根據情況不斷更新low的值。
假設由頂點U訪問到頂點V。當從頂點V回溯到頂點U時，
如果
dfn[v] < low[u]
那麼
low[u] = dfn[v]
如果頂點U還有它分支，每個分支回溯時都進行上述操作，那麼頂點low[u]就表示了不通過頂點U的父節點所能訪問到的最早祖先節點。
4.3 parent數組
parent[]:下標表示頂點的編號，數組中的值表示該頂點的父頂點編號，它主要用於更新low值的時候排除父頂點，當然也可以其它的辦法實現相同的功能。
4.4 一個具體的例子
現在我們來看一個例子，模仿程式計算各個頂點的dfn值和low值。下圖中藍色實線箭頭表示已訪問過的路徑，無箭頭虛線表示未訪問路徑。已訪問過的頂點用黃色標記，未訪問的頂點用白色標記，DFS當前正在處理的頂點用綠色表示。帶箭頭的藍色虛線表示DFS回溯時的返迴路徑。
1）
當DFS走到頂點H時，有三個分支，我們假設我們先走H-I，然後走H-F，最後走H-J。從H訪問I時，頂點I未被訪問過，所以I的dfn和low都為9。根據DFS的遍歷順序，我們應該從頂點I繼續訪問。
2）
上圖表示由頂點I訪問頂點D，而此時發現D已被訪問，當從D回溯到I時，由於
dfn[D] < dfn[I]
說明D是I的祖先頂點，所以到現在為止，頂點I不經過父頂點H能訪問到的小時間戳為4。
3）
根據DFS的原理，我們從頂點I回到頂點H，顯然到目前為止頂點H能訪問到的最小時間戳也是4（因為我們到現在為止只知道能從H可以通過I訪問到D），所以low[H] = 4
4）
現在我們繼續執行DFS，走H-F路徑，發現頂點F已被訪問且dfn[F] < dfn[H]，說明F是H的祖先頂點，但此時頂點H能訪問的最早時間戳是4，而F的時間戳是6，依據low值定義low[H]仍然為4。
5）
最後我們走H-J路徑，頂點J未被訪問過所以 dfn[J] = 10 low[J] = 10
6）
同理，由DFS訪問頂點B，dfn[J] > dfn[B]，B為祖先頂點，頂點J不經過父頂點H能訪問到的最早時間戳就是dfn[B]，即low[J] = 2
7）
我們從頂點J回溯到頂點H，顯然到目前為止頂點H能訪問到的最早時間戳就更新為2（因為我們到現在為止知道了能從H訪問到J），所以low[H] = 2
8）
根據DFS原理，我們從H回退到頂點E（H回退到G,G回退到F，F回退到E的過程省略），所經過的頂點都會更新low值，因為這些頂點不用通過自己的父頂點就可以和頂點B相連。當回溯到頂點E時，還有未訪問過的頂點，那麼繼續進行E-K分支的DFS。
9）
從E-K分支訪問到頂點L時，頂點k和L的的dfn值和low值如圖上圖所示
10）
接著我們繼續回溯到了頂點D（中間過程有所省略），並更新low[D]
11）
最後，按照DFS的原理，我們回退到頂點A，並且求出來了每個頂點的dfn值和low值。
4.5 割點及橋的判定方法
割點：判斷頂點U是否為割點，用U頂點的dnf值和它的所有的孩子頂點的low值進行比較，如果存在至少一個孩子頂點V滿足low[v] >= dnf[u]，就說明頂點V訪問頂點U的祖先頂點，必須通過頂點U，而不存在頂點V到頂點U祖先頂點的其它路徑，所以頂點U就是一個割點。對於沒有孩子頂點的頂點，顯然不會是割點。
橋（割邊）：low[v] > dnf[u] 就說明V-U是橋
需要說明的是，Tarjan演算法從圖的任意頂點進行DFS都可以得出割點集和割邊集。
從上圖的結果中我們可以看出，頂點B,頂點E和頂點K為割點，A-B以及E-K和K-L為割邊。
5. 代碼實現
package datastruct;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.PrintWriter;
import java.io.Reader;
import java.io.StringWriter;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class CutVerEdge {
/*用於標記已訪問過的頂點*/
private boolean[] marked;
/*三個數組的作用不再解釋*/
private int[] low;
private int[] dfn;
private int[] parent;
/*用於標記是否是割點*/
private boolean[] isCutVer;
/*存儲割點集的容器*/
private List<Integer> listV;
/*存儲割邊的容器，容器中存儲的是數組，每個數組只有兩個元素，表示這個邊依附的兩個頂點*/
private List<int[]> listE;
private UndirectedGraph ug;
private int visitOrder;/*時間戳變數*/
/*定義圖的邊*/
public static class Edge{
/*邊起始頂點*/
private final int from;
/*邊終結頂點*/
private final int to;
public Edge(int from, int to){
this.from = from;
this.to= to;
}
public int from(){
return this.from;
}
public int to(){
return this.to;
}
public String toString(){
return "[" + from + ", " + to +"] ";
}
}
/*定義無向圖*/
public static class UndirectedGraph{
private int vtxNum;/*頂點數量*/
private int edgeNum;/*邊數量*/
/*臨接表*/
private LinkedList<Edge>[] adj;
/*無向圖的構造函數,通過txt文件構造圖，無權值*/
@SuppressWarnings("unchecked")
public UndirectedGraph(Reader r){
BufferedReader br = new BufferedReader(r);
Scanner scn = new Scanner(br);
/*圖中頂點數*/
vtxNum = scn.nextInt();
/*圖中邊數*/
edgeNum = scn.nextInt();
adj = (LinkedList<Edge>[])new LinkedList[vtxNum];
for(int i = 0; i < vtxNum; i++){
adj[i] = new LinkedList<Edge>();
}
/*無向圖,同一條邊，添加兩次*/
for(int i = 0; i < edgeNum; i++){
int from = scn.nextInt();
int to = scn.nextInt();
Edge e1 = new Edge(from, to);
Edge e2 = new Edge(to, from);
adj[from].add(e1);
adj[to].add(e2);
}
scn.close();
}
/*圖的顯示方法*/
@Override
public String toString(){
StringWriter sw = new StringWriter();
PrintWriter pw = new PrintWriter(sw);
for (int i = 0; i < vtxNum; i++) {
pw.printf(" %-3d: ", i);
for (Edge e : adj[i]) {
pw.print(e);
}
pw.println();
}
return sw.getBuffer().toString();
}
/*返回頂點個數*/
public int vtxNum(){
return vtxNum;
}
/*返回邊的數量*/
public int edgeNum(){
return edgeNum;
}
}
public CutVerEdge(UndirectedGraph ug){
this.ug = ug;
marked = new boolean[ug.vtxNum()];
low = new int[ug.vtxNum()];
dfn = new int[ug.vtxNum()];
parent = new int[ug.vtxNum()];
isCutVer = new boolean[ug.vtxNum()];
listV = new LinkedList<Integer>();
listE = new LinkedList<int[]>();
/*調用深度優先遍歷，求解各個頂點的dfn值和low值*/
dfs();
}
private void dfs(){
int childTree = 0;
marked[0] = true;
visitOrder = 1;
parent[0] = -1;
for(Edge e : ug.adj[0]){
int w = e.to();
if(!marked[w]){
marked[w] = true;
parent[w] = 0;
dfs0(w);
/*根頂點相連的邊是否是橋*/
if(low[w] > dfn[0]){
listE.add(new int[]{0, w});
}
childTree++;
}
}
/*單獨處理根頂點*/
if(childTree >= 2){/*根頂點是割點的條件*/
isCutVer[0] = true;
}
}
/*除了根頂點的其它情況*/
private void dfs0(int v){
dfn[v] = low[v] = ++visitOrder;
for(Edge e : ug.adj[v]){
int w = e.to();
if(!marked[w]){
marked[w] = true;
parent[w] = v;
dfs0(w);
low[v] = Math.min(low[v], low[w]);
/*判斷割點*/
if(low[w] >= dfn[v]){
isCutVer[v] = true;
/*判斷橋*/
if(low[w] > dfn[v]){
listE.add(new int[]{v, w});
}
}
}else
if(parent[v] != w && dfn[w] < dfn[v]){
low[v] = Math.min(low[v], dfn[w]);
}
}
}
/*返回所有割點*/
public List<Integer> allCutVer(){
for(int i = 0; i < isCutVer.length; i++){
if(isCutVer[i]){
listV.add(i);
}
}
return listV;
}
/*返回所有割邊*/
public List<int[]> allCutEdge(){
return listE;
}
/*判斷頂點v是否是割點*/
public boolean isCutVer(int v){
return isCutVer[v];
}
public static void main(String[] args) throws FileNotFoundException{
File path = new File(System.getProperties()
.getProperty("user.dir"))
.getParentFile();
File f = new File(path, "algs4-data/tinyG2.txt");
FileReader fr = new FileReader(f);
UndirectedGraph ug = new UndirectedGraph(fr);
System.out.println("\n-------圖的鄰接表示法-------");
System.out.println(ug);
System.out.println("\n-------圖中的割點-------");
CutVerEdge cve = new CutVerEdge(ug);
for(int i : cve.allCutVer()){
System.out.println(i);
}
System.out.println("\n-------圖中的割邊-----");
for(int[] a : cve.allCutEdge()){
System.out.println(a[0]+" "+ a[1]);
}
}
}
運行結果
------圖的鄰接表示法------- 0 : [0, 5] [0, 1] [0, 2] [0, 6] 1 : [1, 0] 2 : [2, 0] 3 : [3, 4] [3, 5] 4 : [4, 3] [4, 6] [4, 5] 5 : [5, 0] [5, 4] [5, 3] 6 : [6, 4] [6, 7] [6, 9] [6, 0] 7 : [7, 8] [7, 6] 8 : [8, 7] 9 : [9, 12] [9, 10] [9, 11] [9, 6] 10 : [10, 9] 11 : [11, 12] [11, 9] 12 : [12, 9] [12, 11] -------圖中的割點------- 0 6 7 9 -------圖中的割邊----- 7 8 6 7 9 10 6 9 0 1 0 2
6. 參考內容
[1]. http://www.cnblogs.com/en-heng/p/4002658.html
[2]. http://blog.csdn.net/wtyvhreal/article/details/43530613
[3]. http://www.cppblog.com/ZAKIR/archive/2010/08/30/124869.html?opt=admin
