強連結成分

DFS ベースの線形時間アルゴリズム

深さ優先探索に基づくいくつかのアルゴリズムが、線形時間で強連結成分を計算する。

• コサラジュのアルゴリズムは2回の深さ優先探索を使用する。1回目は元のグラフに対するものであり、2回目の深さ優先探索の外側ループが各頂点を既訪問かどうか調べ、未訪問なら再帰的に探索する際の頂点の順序を選ぶために用いられる。2回目の深さ優先探索は元のグラフの転置グラフに対して行われ、再帰探索ごとに1つの新しい強連結成分が見つかる^[2][3]。 この名前は S. ラオ・コサラジュにちなむ。彼は1978年にこの方法を記述した（ただし結果を出版しなかった）が、後に1981年にミハ・シャリルが出版した^[4]。
• ロバート・タージャンが1972年に発表した^[5]タージャンの強連結成分アルゴリズムは、深さ優先探索を1回だけ行う。このアルゴリズムは、探索によって訪問されたもののまだ成分に割り当てられていない頂点のスタックを保持し、各頂点の「low number」（その頂点の子孫から1ステップで到達できる最も高い祖先のインデックス番号）を計算し、それを用いていつ頂点集合をスタックから取り出して新しい成分とするかを決定する。
• 経路ベース強連結成分アルゴリズムは、タージャンのアルゴリズムと同様に深さ優先探索を用いるが、スタックを2つ使う。一方のスタックはまだ成分に割り当てられていない頂点を追跡するために使われ、もう一方は深さ優先探索木における現在の経路を追跡する。このアルゴリズムの最初の線形時間版は、1976年にエドガー・ダイクストラによって発表された^[6]。

コサラジュのアルゴリズムは概念的に単純であるが、タージャンのアルゴリズムおよび経路ベースのアルゴリズムは、2回ではなく1回の深さ優先探索だけで済む。

到達可能性ベースのアルゴリズム

従来の線形時間アルゴリズムは一般に並列化が難しいとされる深さ優先探索に基づいている。Fleischer ら^[7]は2000年に到達可能性クエリに基づく分割統治アプローチを提案し、この種のアルゴリズムは通常、到達可能性ベース SCC アルゴリズムと呼ばれる。このアプローチの考え方は、ランダムにピボット頂点を選び、その頂点から前方および後方の到達可能性クエリを適用するものである。2つのクエリは頂点集合を4つの部分集合に分割する。すなわち、両方の探索で到達される頂点、どちらか一方のみで到達される頂点、どちらでも到達されない頂点である。ある強連結成分はこれらの部分集合のいずれかに含まれなければならないことを示せる。両方の探索で到達される頂点部分集合がひとつの強連結成分をなし、アルゴリズムは残りの3つの部分集合に対して再帰する。

このアルゴリズムの期待逐次実行時間は O(n log n) であることが示されており、古典的なアルゴリズムより O(log n) 倍遅い。並列性は次の2点から生まれる。(1) 到達可能性クエリはより並列化しやすく（例えば幅優先探索 (BFS) を用いると、グラフの直径が小さければ高速化できる）、(2) 分割統治過程における部分課題間の独立性がある。 このアルゴリズムは現実世界のグラフでは良好に動作する^[3]が、並列性に関する理論的な保証はない（辺を1つも持たないグラフの場合、アルゴリズムは O(n) 段階の再帰を必要とする）。

Blelloch ら^[8]は2016年に、到達可能性クエリをランダムな順序で適用するならば O(n log n) のコスト限界が依然として成り立つことを示した。さらに、クエリは接頭辞倍増方式（すなわち 1, 2, 4, 8 個のクエリ）でバッチ処理でき、1ラウンドで同時に実行できる。このアルゴリズムの全体的なspanは log₂ n 回の到達可能性クエリであり、これはおそらく到達可能性ベースのアプローチで達成できる最適な並列性である。

ランダムな強連結グラフの生成

Peter M. Maurer は、ランダムな強連結グラフを生成するアルゴリズム^[9]を記述している。これは、グラフを強連結にするために追加すべき辺数を最小化する問題である強連結性拡張のアルゴリズムを改変したものに基づいている。ノードの再ラベル付けと組み合わせて Gilbert モデルや Erdős–Rényi モデルと共に使用すると、このアルゴリズムは生成できる構造の種類を制限することなく、n 頂点上の任意の強連結グラフを生成することができる。