本頁使用了標題或全文手工轉換

強連通元件

維基百科,自由的百科全書
跳至導覽 跳至搜尋

強連通元件英語Strongly connected component)是圖論中的概念。圖論中,強連通圖指每一個頂點皆可以經由該圖上的邊抵達其他的每一個點的有向圖。意即對於此圖上每一個點對(Va,Vb),皆存在路徑Va→Vb以及Vb→Va強連通元件則是指一張有向圖G的極大強連通子圖G'。如果將每一個強連通元件縮成一個點,則原圖G將會變成一張有向無環圖。一張圖被稱為有向無環圖若且唯若此圖不具有點集合數量大於一的強連通分量,因為有向環即是一個強連通元件,而且任何的強連通元件皆具有至少一個有向環。

Kosaraju算法Tarjan算法Gabow算法英語Gabow's algorithm皆為尋找有向圖強連通元件的有效算法。但是由於在Tarjan算法和Gabow算法的過程中,只需要進行一次的深度優先搜索,因而相對Kosaraju算法較有效率。

另一類常用的算法[1] 是基於連通性查詢的分支算法實現。在串行的情況下算法的復雜度為O(n log n ),但是卻可以達到很好的並行性。Blelloch等人[2]證明了此算法在最壞情況下依然有很高的並行度(算法的span英語Analysis of parallel algorithms僅為 log2 n 次查詢)。

尋找強連通分量的演算法,也可以用來解2-SAT英語2-satisfiability(2-satisfiability)問題。Aspvall, Plass & Tarjan (1979)

根據Robbins理論英語Robbins' theorem,當一個無向圖為雙連接圖時,也會形成強連通。

參見[編輯]

參考[編輯]

  • ^ Fleischer, Lisa K; Hendrickson, Bruce; and Pinar, Ali. On identifying strongly connected components in parallel. IPDPS 2000.
  • ^ Blelloch, Guy; Gu, Yan; Shun, Julian; and Sun, Yihan. Parallelism in Randomized Incremental Algorithms. SPAA 2016. doi:10.1145/2935764.2935766.