グラフ / Topological Sort（トポロジカルソート）

依存関係を壊さずに
順序を作る。

有向非巡回グラフの頂点を、辺の向きを保ったまま並べる方法です。タスク依存の可視化に向いています。

グラフノードとエッジ可視化向き

このページの目次

このページでわかること概要擬似コード要点まとめ動きで確認次に見るページ

このページでわかること

先に知っておくポイント

1. どの頂点が注目か

2. 候補集合がどう変わるか

3. なぜ次の頂点や辺を選ぶか

概要

有向非巡回グラフの頂点を、辺の向きを保ったまま並べる方法です。タスク依存の可視化に向いています。

考え方

擬似コード

compute indegrees
push indegree-0 nodes
pop and remove outgoing edges

要点

要点まとめ

時間計算量

O(V + E)

前提

DAG

方法

入次数管理

用途

依存解決

補足

向いている場面と注意点

何が嬉しいか

前提タスクを先に終える順番が得られます。

循環

閉路があると並べられません。

見せ方

入次数 0 の頂点がどんどん出てくる流れを見せます。

動きで確認

動きを見てたしかめる

ここでは「どの頂点が注目か」を見ながら、上で読んだ内容を動きと結びつけます。

注目候補確定

次に見る

次に見るページ

比較すると違いがわかりやすいページを先に置いています。

Prim（プリム法）を見る

依存関係を壊さずに順序を作る。