\( \newcommand{\ord}[1]{\mathcal{O}\left(#1\right)} \newcommand{\abs}[1]{\lvert #1 \rvert} \newcommand{\floor}[1]{\lfloor #1 \rfloor} \newcommand{\ceil}[1]{\lceil #1 \rceil} \newcommand{\opord}{\operatorname{\mathcal{O}}} \newcommand{\argmax}{\operatorname{arg\,max}} \newcommand{\str}[1]{\texttt{"#1"}} \)

2016年1月3日 星期日

[ Bridge & Bridge-connected Component ] 橋和橋連通分量(BCC)

只要從一張無向圖上移除了橋，就會讓這張圖分離成更多部分，呈現不連通的狀態。
注意！必須要考慮重邊的問題:
  1. 對於有向圖的強連通分量，重邊是沒有影響的，因為強連通只要求任意兩點可以互相連通
  2. 對於無向圖的點雙連通分量，重邊也是沒有影響的，因為點雙連通要求是任意兩點之間至少存在兩條點不重複的路徑，對邊的重複並沒有要求
  3. 對於無向圖的邊雙連通分量，重邊就有影響了，因為邊雙連通要求任意兩點之間至少存在兩條邊不重複的路徑
這裡提供模板:

一張無向圖上，不會產生橋的連通分量，稱作橋連通分量，或是橋雙連通分量
這裡提供模板，code跟橋差不多，只是需要用堆疊去記錄當前節點而已:


張貼者： 於
標籤：

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)