圖的O（m + n）時間算法

我剛剛開始學習關於圖的知識，似乎無法爲此問題想出一個算法，甚至不知道從哪裏開始。我將衷心感謝您的幫助！對於給定的連通圖G =（V，E），設計O（n + m）時間算法以找到節點v∈V，因此移除v及其所有相鄰邊將不會斷開連接G.圖的O（m + n）時間算法

預先感謝您！

來源

2017-02-12 CSstudent

執行圖的寬度優先搜索。找到的最後一個節點可以在不斷開圖形的情況下被移除。

證明：BFS生成圖的生成樹，找到的最後一個節點始終是該樹的葉。移除生成樹的樹葉不會斷開樹，並留下剩餘頂點的生成樹。

來源

2017-02-12 23:01:11

這只是一個局部解決方案 - 在BFS樹中可以有更多的關節點，刪除該關節點將從該樹的主體斷開以該頂點爲根的子樹。 – MT0

@ MT0我不太清楚你的意思。您是否誤解了「將斷開G」而不是「不會斷開G」的問題？ –

如果您找到所有關節點，那麼任何非關節點都將成爲雙連通組件的一部分，如果它們被移除，則不會斷開圖形。執行BFS並取走葉子將無法找到圖中的所有非關節點。 – MT0

一個頂點可以被移除（沒有斷開的曲線圖的其餘部分），如果：

它不是一個鉸接點;或
它終止圖中的路徑，該路徑只在一端連接;或
它是圖中唯一的頂點。

一種算法參見Hopcroft, J.; Tarjan, R. (1973). "Algorithm 447: efficient algorithms for graph manipulation". Communications of the ACM. 16 (6): 372–378識別鉸接點：

執行圖表上的深度優先搜索 - 下面是一個遞歸DFS算法一些僞代碼：

procedure RecursiveDFS (u) { 
    mark u as visited 
    u.index = u.lowPoint = ++global_index 
    if ( (u is the root and has zero connected edges) 
     or (u is not the root and has one connected edge)) { 
    mark u as a leaf 
    } 
    for each (edge e connected to u) { 
    if (e is unvisited) { 
     mark e as visited 
     let e = {u , v} 
     if (v is unvisited) { 
     mark e as tree edge 
     RecursiveDFS (v) 
     if (v.lowPoint < u.lowPoint) 
     { 
      u.lowPoint = v.index 
     } else { 
      mark u as an articulation-point 
     } 
     } else { 
     mark e as cotree edge 
     if (v.index < u.lowPoint) 
     { 
      u.lowPoint = v.index 
     } 
     } 
    } 
    } 
}

這將訪問每個頂點和每個邊一次O(m+n)，並且如果在給定頂點處存在以該頂點爲根的DFS的子樹（其不具有從該子樹發出的共樹（後）邊），則將頂點標記爲關節點連接到給定的verte的祖先X。

特殊情況是根頂點（您開始DFS的地方），它始終會被標記爲關節點（因爲它沒有祖先供子樹連接） - 相反，您應該檢查根頂點只有一個相鄰的樹邊和一個或多個相鄰的共樹（後）邊（並且是雙連通分量的一部分）。

頂點終止的路徑要麼是：

的DFS樹的葉頂點（正好與一個連接樹邊緣，從DFS樹中的父，並且零連接共樹邊緣） ;或者
DFS樹的根頂點一個相鄰的樹邊和零個相鄰的共樹（後）邊。

來源

2017-02-14 15:30:29 MT0

圖的O（m + n）時間算法

回答

相關問題