强连通分量

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

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

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

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

根據Robbins理论，當一個無向圖為雙連接圖時，也會形成強連通。