用於查找關節點或切割圖的頂點的算法的說明

Question

我搜索了網絡，找不到DFS算法的任何解釋來查找圖的所有關節頂點。甚至沒有維基頁面。

從閱讀中，我瞭解了這裏的基本事實。 PDF

在每個節點上都有一個變量，它實際上是在查看後端邊緣並找到朝向根節點的最近和最上方的節點。在處理完所有邊後，將會找到它。

但我不明白如何在執行DFS期間在每個節點上找到這個向上變量&。這個變量究竟在做什麼？

請說明算法。

謝謝。

Answer 1

查找關節頂點是DFS的應用程序。

簡而言之，

1. 應用上的曲線圖的DFS。獲取DFS樹。
2. 較早訪問的節點是那些到達並稍後訪問的節點的「父」。
3. 如果一個節點的任何孩子沒有到其父代的任何祖先的路徑，這意味着刪除這個節點會使這個孩子與圖表分離。
4. 有一個例外：樹的根。如果它有不止一個孩子，那麼它是一個關節點，否則不是。

點3本質上意味着這個節點是一個關節點。

現在對於一個孩子來說，這條通往節點祖先的路徑將通過它的後端或其任何子節點。

所有這一切在這PDF精美地解釋。

Answer 2

如果u後代的low大於u的dfsnum大，那麼u據說是關節點。

int adjMatrix[256][256]; 
int low[256], num=0, dfsnum[256]; 

void cutvertex(int u){ 
    low[u]=dfsnum[u]=num++; 
    for (int v = 0; v < 256; ++v) 
    { 
     if(adjMatrix[u][v] && dfsnum[v]==-1) 
     { 
      cutvertex(v); 
      if(low[v]>dfsnum[u])  
       cout<<"Cut Vertex: "<<u<<"\n"; 
      low[u]=min(low[u], low[v]); 
     } 
     else{ 
      low[u]=min(low[u], dfsnum[v]); 
     } 
    } 
} 

Answer 3

我會盡力制定關於如何算法的工作一個直觀的瞭解，並給予評論僞輸出雙組件以及橋樑。

實際上很容易爲關節點開發一個強力算法。只需取出一個頂點，然後在圖上運行BFS或DFS。如果它保持連接，那麼頂點不是關節點，否則是。這將運行在O(V(E+V)) = O(EV)時間。面臨的挑戰是如何在線性時間內做到這一點（即O(E+V)）。

鉸接點連接兩個（或更多）子圖。這意味着從一個子圖到另一個子圖沒有邊。所以想象你在這些子圖之一內並訪問它的節點。在您訪問節點時，您會標記該節點，然後使用某個可用邊移動到下一個無標記節點。當你這樣做時，你怎麼知道你還在同一個子圖裏？這裏的見解是，如果你在同一個子圖中，你最終將在訪問一個未被標記的節點時通過邊緣看到一個被標記的節點。這被稱爲後沿，表明你有一個循環。一旦找到後端邊緣，您可以確信，通過該標記節點的所有節點到您正在訪問的節點都是同一子圖的一部分，並且兩者之間沒有關聯點。如果您沒有看到任何後緣，那麼到目前爲止您訪問的所有節點都是關節點。

所以我們需要爲當前存在訪問過節點返回邊緣的目標之間的訪問頂點和標記所有點爲同一子圖內的算法。子圖中顯然可能有子圖，所以我們需要選擇我們迄今爲止最大的子圖。這些子圖被稱爲雙組分。我們可以通過爲每個雙分量分配一個初始化的ID作爲我們到目前爲止訪問的頂點數量的計數來實現這個算法。後來，當我們找到邊緣時，我們可以將雙親ID重置爲迄今爲止我們發現的最低。

我們顯然需要兩遍。在第一遍中，我們想要確定哪個頂點可以通過後邊緣從每個頂點看到，如果有的話。在第二遍中，我們希望訪問相反方向的頂點並收集最小的雙組分ID（即可從任何後代訪問的最早的祖先）。 DFS自然適合這裏。在DFS中，我們先下去，然後再回來，所以上述兩個過程都可以在單個DFS遍歷中完成。

現在事不宜遲，這裏的僞代碼：

time = 0 
visited[i] = false for all i 
GetArticulationPoints(u) 
    visited[u] = true 
    u.st = time++ 
    u.low = v.st //keeps track of highest ancestor reachable from any descendants 
    dfsChild = 0 //needed because if no child then removing this node doesn't decompose graph 
    for each ni in adj[i] 
     if not visited[ni] 
      GetArticulationPoints(ni) 
      ++dfsChild 
      parents[ni] = u 
      u.low = Min(u.low, ni.low) //while coming back up, get the lowest reachable ancestor from descendants 
     else if ni <> parent[u] //while going down, note down the back edges 
      u.low = Min(u.low, ni.st) 

    //For dfs root node, we can't mark it as articulation point because 
    //disconnecting it may not decompose graph. So we have extra check just for root node. 
    if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1) 
     Output u as articulation point 
     Output edges of u with v.low >= u.low as bridges 
    output u.low as bicomponent ID