有向グラフとトポロジカルソート ― 順序構造としてのグラフ

強連結成分（SCC），TarjanおよびKosarajuのアルゴリズム，DAGとトポロジカルソート，半順序との対応，DAG上のDPを解説する．

2026年2月27日

1 有向グラフにおける到達可能性

定義 1 (到達可能性).

有向グラフ

G = (V, A)

において，頂点

u

から頂点

v

への有向路が存在するとき，

v

は

u

から到達可能であるといい，

u ⇝ v

と書く．

定義 2 (強連結).

有向グラフ

G

の2頂点

u, v

が相互到達可能であるとは，

u ⇝ v

かつ

v ⇝ u

が成り立つことをいう．

G

のすべての2頂点が相互到達可能であるとき，

G

を強連結（strongly connected）であるという．

定理 3 (相互到達可能性は同値関係).

V

上の関係「

u

と

v

は相互到達可能」は同値関係である．

証明.

反射性：長さ

0

の路により

u ⇝ u

．対称性：定義より明らか．推移性：

u ⇝ v

かつ

v ⇝ w

ならば路の連結で

u ⇝ w

．逆向きも同様． □

2 強連結成分とSCC縮約

定義 4 (強連結成分).

上の同値関係による

V

の同値類を

G

の強連結成分（strongly connected component, SCC）という．

定理 5 (SCC 縮約は DAG).

各 SCC を

1

つの頂点に縮約して得られるグラフ

G^{SCC}

は DAG（有向非巡回グラフ）である．

証明.

G^{SCC}

に有向閉路

C_{1} \to C_{2} \to \dots \to C_{k} \to C_{1}

が存在すると仮定する．

C_{i}

内の任意の頂点

u

と

C_{j}

内の任意の頂点

v

に対し，

C_{i}

から

C_{j}

への路と

C_{j}

から

C_{i}

への路が（SCC 内部の路を経由して）構成できる．よって

u

と

v

は相互到達可能であり，

C_{i}

と

C_{j}

は同じ SCC に属する．これは

C_{i} \neq = C_{j}

に矛盾する． □

3 深さ優先探索（DFS）

有向グラフの構造解析に不可欠な手法が DFS（深さ優先探索）である．

アルゴリズム 1: 深さ優先探索 (DFS)

Input:

有向グラフ

G = (V, A)

Output:

各頂点の発見時刻

disc [v]

，終了時刻

fin [v]

for all

v \in V

visited [v] \leftarrow false

end for

time \leftarrow 0

for all

v \in V

\neg visited [v]

DFS-Visit(

G, v

)

end if

end for

procedure DFS-Visit

G, u

visited [u] \leftarrow true

time \leftarrow time + 1

disc [u] \leftarrow time

for all

(u, v) \in A

\neg visited [v]

DFS-Visit(

G, v

)

end if

end for

time \leftarrow time + 1

fin [u] \leftarrow time

end procedure

DFS の計算量は $O (∣ V ∣ + ∣ A ∣)$ であり，帰りがけ時刻の降順がトポロジカルソートを与える．

4 Kosaraju のアルゴリズム

Kosaraju のアルゴリズムは， $G$ の逆グラフ $G^{R}$ （すべての辺の向きを反転したもの）を利用して SCC を $O (∣ V ∣ + ∣ A ∣)$ で求める．

$G$ 上で DFS を行い，帰りがけ順（finish time の降順）に頂点を並べる．
$G^{R}$ 上で，上の順に未訪問の頂点から DFS を行う． $1$ 回の DFS で訪問した頂点集合が $1$ つの SCC である．

定理 6 (Kosaraju の正当性).

上のアルゴリズムで得られる各頂点集合は，

G

の強連結成分に一致する．

証明.

ステップ 1 で帰りがけ時刻が最大の頂点は，SCC 縮約 DAG においてソース（入次数

0

）の SCC に属する．ステップ 2 で

G^{R}

上の DFS を行うと，この SCC 内の頂点のみが訪問される（

G^{R}

上で他の SCC への到達は SCC 縮約の向きが逆転しているため不可能）．帰納的に，SCC 縮約の逆トポロジカル順に SCC が正しく分離される． □

5 Tarjan のアルゴリズム

Tarjan のアルゴリズムは DFS $1$ 回で SCC を求める．各頂点 $v$ に DFS 発見時刻 $disc [v]$ と， $v$ の DFS 部分木から後退辺を通じて到達できる頂点の最小発見時刻 $low [v]$ を管理する． $disc [v] = low [v]$ となる頂点 $v$ が SCC のルートであり，その時点でスタック上の $v$ 以降の頂点が $1$ つの SCC を構成する．

注意 7.

Tarjan のアルゴリズムも計算量は

O (∣ V ∣ + ∣ A ∣)

であり，逆グラフの構築が不要な分，実装上は Kosaraju より定数倍が軽い場合がある．

6 トポロジカルソート

定義 8 (トポロジカルソート).

DAG

G = (V, A)

のトポロジカルソートとは，

V

の全順序

v_{1}, v_{2}, \dots, v_{n}

であって，すべての弧

(v_{i}, v_{j}) \in A

に対して

i < j

が成り立つものをいう．

定理 9 (トポロジカルソートの存在).

有向グラフ

G

がトポロジカルソートを持つための必要十分条件は，

G

が DAG であることである．

証明.

(\Rightarrow)

：

G

に有向閉路

v_{i_{1}} \to v_{i_{2}} \to \dots \to v_{i_{k}} \to v_{i_{1}}

が存在すれば

i_{1} < i_{2} < \dots < i_{k} < i_{1}

となり矛盾．

(\Leftarrow)

：DAG には入次数

0

の頂点が存在する（すべての頂点の入次数が正なら，任意の頂点から入辺を辿り続けて有向閉路が構成される）．入次数

0

の頂点を列の先頭に置き，除去して残りのグラフ（これも DAG）に帰納法を適用する． □

注意 10.

DFS の帰りがけ時刻の降順がトポロジカルソートを与える．これは

O (∣ V ∣ + ∣ A ∣)

で計算可能である．あるいは，入次数

0

の頂点をキューで管理する BFS ベースの方法（Kahn のアルゴリズム）も同じ計算量で動作する．

7 半順序との対応

注意 11.

DAG は半順序集合の Hasse 図と見なせる．DAG 上の到達可能性関係は反射的・反対称的・推移的であり，半順序の公理を満たす．トポロジカルソートとは，この半順序の線形拡大（任意の半順序に矛盾しない全順序への拡張）に他ならない．線形拡大の存在は Szpilrajn の定理として知られる．

8 DAG 上の動的計画法

DAG 上では，トポロジカル順に処理することで多くの最適化問題が動的計画法で解ける．

例 12 (DAG 上の最長路).

各頂点

v

に対して

ℓ [v]

を

s

から

v

への最長路の長さとする．トポロジカル順に

ℓ [v] = (u, v) \in A max (ℓ [u] + w (u, v))

を計算すれば

O (∣ V ∣ + ∣ A ∣)

で全頂点の最長路が求まる．これは負の重みがあっても正しく動作する（閉路がないため）．

例 13 (DAG 上の経路数).

s

から各頂点

v

への経路の総数

c [v]

も，トポロジカル順に

c [v] = (u, v) \in A \sum c [u]

と計算できる（

c [s] = 1

，

s

から到達不能な

v

については

c [v] = 0

）．

注意 14.

SCC 縮約と DAG 上の DP を組み合わせることで，一般の有向グラフ上の問題を「SCC 内部の処理」と「SCC 間の順序に沿った DP」に分離できる．これは有向グラフ上のアルゴリズム設計における基本的なパラダイムである．

グラフ理論離散数学教科書強連結成分トポロジカルソート DAG

Folio公式

数学の「教科書が書かない行間」をLaTeXで．Folio公式アカウントです．

0 followers·105 articles

有向グラフとトポロジカルソート ― 順序構造としてのグラフ

1 有向グラフにおける到達可能性

2 強連結成分とSCC縮約

3 深さ優先探索（DFS）

4 Kosaraju のアルゴリズム

5 Tarjan のアルゴリズム

6 トポロジカルソート

7 半順序との対応

8 DAG 上の動的計画法

Share your expertise with the world

More from Folio公式

Folio LaTeXの基本 ― 標準LaTeXとの違いと始め方

カタラン数はなぜどこにでも現れるのか ― 括弧列・二分木・格子経路の不思議な一致

漸化式と母関数 ― 数列を「関数」にすると何が見えるか

包除原理はなぜ「足して引いて」を繰り返すのか ― ベン図からメビウス関数へ