【とぽろじかるそーと】
トポロジカルソート とは？
最終更新:
💡 先に必要なことを守って、順番を作る
有向非巡回グラフの頂点を、各辺の始点が終点より先になるように並べること。作業の前提条件を守る順番を求められ、条件次第では複数の正しい並び方がある。
📌 このページのポイント
- 辺の始点が終点より先になるように並べる
- 全頂点を並べられるのは、有向の循環がない場合
- 依存関係のない作業の順番は、一通りとは限らない
- 順番を求めることと、実際に作業を実行することは別
ひよこ 普通のソートと何が違うの？
ペンギン先生 ひよこ 正しい順番は、一つだけ？
ペンギン先生 一つとは限らないよ。Aの後にBとC、その両方の後にDなら、A→B→C→DもA→C→B→Dも条件を満たす。BとCの前後は決められていないんだ。必要な前後関係と、自由に選べる順番を分けると分かりやすいね。
ひよこ どうやって、順番を作るの？
ペンギン先生 例えば、まだ前提のない頂点を取り出し、それを除いた残りから次を探す方法があるよ。Pythonのgraphlibも、前提が済んで処理できる頂点をget_readyで取り出せる。複数の頂点が準備できたら、処理する順番や並列実行は別に決めるんだ。
ひよこ 循環依存があったら？
ペンギン先生 Aの前にB、Bの前にAが必要なら、その全体を条件どおりに並べられないよ。PythonではCycleErrorで循環を知らせる。一部に循環があっても、依存していない部分は処理できる場合がある。まず循環を解消する必要がある範囲を確認しよう。
まとめ：ざっくりこれだけ覚えればOK！
「トポロジカルソート」って出てきたら「先に必要な作業を守る順番に並べること」と思えばだいたいOK！
📖 おまけ：英語の意味
「Topological Sort」 ＝ 位相的な順序付け
💬 グラフの向きに沿う前後関係を保つ並べ方だよ。名前の由来を推測するより、矢印が何を表すかを確認しよう。