数学における有向グラフの理論において、任意の頂点から他のすべての頂点へ到達できるとき、そのグラフは強連結（きょうれんけつ、）であるという。有向グラフの強連結成分（きょうれんけつせいぶん、）とは、グラフをそれ自身が強連結であるような部分グラフへと分割したものである。グラフの強連結性を判定したり、強連結成分を求めたりすることは、線形時間（すなわち Θ(V + E)）で行うことができる。
定義 有向グラフが強連結であるとは、グラフの任意の2頂点の組の間に、互いの方向に道が存在することである。すなわち、組の一方の頂点から他方の頂点への道が存在し、かつ逆向きの道も存在するということである。 必ずしも自身は強連結でない有向グラフ G において、2つの頂点 u, v が互いに強連結であるとは、両者の間に各方向について道が存在することをいう。
強連結であるという二項関係は同値関係であり、その同値類の誘導部分グラフが強連結成分と呼ばれる。 同値的に、有向グラフ G の強連結成分とは、強連結である部分グラフのうちこの性質に関して極大なもの、すなわち強連結であるという性質を壊すことなく G から追加の辺や頂点を加えることはできないような部分グラフである。強連結成分の全体は G の頂点集合の分割をなす。強連結成分 C が自明（trivial）であるとは、C が単一の頂点のみからなり、しかもその頂点に自己ループ辺が接続していない場合をいい、そうでないとき非自明（non-trivial）である。
各強連結成分を単一の頂点へ縮約すると、得られるグラフは有向非巡回グラフとなり、これを G の縮約（condensation）と呼ぶ。有向グラフが非巡回的であるのは、複数の頂点を含む強連結部分グラフを持たないとき、かつそのときに限る。なぜなら、有向閉路は強連結であり、非自明な強連結成分は少なくとも1つの有向閉路を含むからである。
アルゴリズム DFS ベースの線形時間アルゴリズム 深さ優先探索に基づくいくつかのアルゴリズムが、線形時間で強連結成分を計算する。 コサラジュのアルゴリズムは2回の深さ優先探索を使用する。1回目は元のグラフに対するものであり、2回目の深さ優先探索の外側ループが各頂点を既訪問かどうか調べ、未訪問なら再帰的に探索する際の頂点の順序を選ぶために用いられる。2回目の深さ優先探索は元のグラフの転置グラフに対して行われ、再帰探索ごとに1つの新しい強連結成分が見つかるThomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Section 22.5, pp. 552–557.。 この名前は S. ラオ・コサラジュにちなむ。彼は1978年にこの方法を記述した（ただし結果を出版しなかった）が、後に1981年にミハ・シャリルが出版した。 ロバート・タージャンが1972年に発表したタージャンの強連結成分アルゴリズムは、深さ優先探索を1回だけ行う。このアルゴリズムは、探索によって訪問されたもののまだ成分に割り当てられていない頂点のスタックを保持し、各頂点の「low number」（その頂点の子孫から1ステップで到達できる最も高い祖先のインデックス番号）を計算し、それを用いていつ頂点集合をスタックから取り出して新しい成分とするかを決定する。 経路ベース強連結成分アルゴリズムは、タージャンのアルゴリズムと同様に深さ優先探索を用いるが、スタックを2つ使う。一方のスタックはまだ成分に割り当てられていない頂点を追跡するために使われ、もう一方は深さ優先探索木における現在の経路を追跡する。このアルゴリズムの最初の線形時間版は、1976年にエドガー・ダイクストラによって発表された.。 コサラジュのアルゴリズムは概念的に単純であるが、タージャンのアルゴリズムおよび経路ベースのアルゴリズムは、2回ではなく1回の深さ優先探索だけで済む。
到達可能性ベースのアルゴリズム
従来の線形時間アルゴリズムは一般に並列化が難しいとされる深さ優先探索に基づいている。Fleischer らは2000年に到達可能性クエリに基づく分割統治アプローチを提案し、この種のアルゴリズムは通常、到達可能性ベース SCC アルゴリズムと呼ばれる。このアプローチの考え方は、ランダムにピボット頂点を選び、その頂点から前方および後方の到達可能性クエリを適用するものである。2つのクエリは頂点集合を4つの部分集合に分割する。すなわち、両方の探索で到達される頂点、どちらか一方のみで到達される頂点、どちらでも到達されない頂点である。ある強連結成分はこれらの部分集合のいずれかに含まれなければならないことを示せる。両方の探索で到達される頂点部分集合がひとつの強連結成分をなし、アルゴリズムは残りの3つの部分集合に対して再帰する。
このアルゴリズムの期待逐次実行時間は O(n log n) であることが示されており、古典的なアルゴリズムより O(log n) 倍遅い。並列性は次の2点から生まれる。(1) 到達可能性クエリはより並列化しやすく（例えば幅優先探索 (BFS) を用いると、グラフの直径が小さければ高速化できる）、(2) 分割統治過程における部分課題間の独立性がある。 このアルゴリズムは現実世界のグラフでは良好に動作するが、並列性に関する理論的な保証はない（辺を1つも持たないグラフの場合、アルゴリズムは O(n) 段階の再帰を必要とする）。
Blelloch ら.は2016年に、到達可能性クエリをランダムな順序で適用するならば O(n log n) のコスト限界が依然として成り立つことを示した。さらに、クエリは接頭辞倍増方式（すなわち 1, 2, 4, 8 個のクエリ）でバッチ処理でき、1ラウンドで同時に実行できる。このアルゴリズムの全体的なspanは log2 n 回の到達可能性クエリであり、これはおそらく到達可能性ベースのアプローチで達成できる最適な並列性である。
ランダムな強連結グラフの生成
Peter M. Maurer は、ランダムな強連結グラフを生成するアルゴリズムを記述している。これは、グラフを強連結にするために追加すべき辺数を最小化する問題である強連結性拡張のアルゴリズムを改変したものに基づいている。ノードの再ラベル付けと組み合わせて Gilbert モデルや Erdős–Rényi モデルと共に使用すると、このアルゴリズムは生成できる構造の種類を制限することなく、n 頂点上の任意の強連結グラフを生成することができる。
応用 強連結成分を求めるアルゴリズムは、2-充足可能性問題（ブール変数の系であって、変数の組の値に対する制約を持つもの）を解くために用いることができる。 が示したように、2-充足可能性のインスタンスが充足不能であるのは、変数 v であって v とその否定がインスタンスの含意グラフの同じ強連結成分に含まれるものが存在するとき、かつそのときに限る.。
強連結成分はまた、2部グラフの辺を、そのグラフの完全マッチングの一部となり得るか否かに従って分類するダルメージ・メンデルソーン分解の計算にも用いられる.。
関連する結果 有向グラフが強連結であるのは、それが耳分解を持つとき、かつそのときに限る。ここで耳分解とは、辺を有向路と閉路の列に分割したものであり、列の最初の部分グラフは閉路であり、それ以降の各部分グラフは、以前の部分グラフと1頂点を共有する閉路であるか、以前の部分グラフと両端点を共有する道である。
ロビンスの定理によれば、無向グラフがそれを強連結にするような向き付けを行うことができるのは、そのグラフが2-辺連結であるとき、かつそのときに限る。この結果を証明する一つの方法は、基礎となる無向グラフの耳分解を求め、各耳を整合的に向き付けることである.。
関連項目 クリーク (グラフ理論) 連結成分 (グラフ理論)
脚注
外部リンク 強連結成分計算のJava実装 - jBPT ライブラリ内（StronglyConnectedComponents クラス参照）。 強連結成分のC++実装