グラフ（基礎）トポロジカルソート

LeetCode 練習問題集

問題	難易度	重要度	テクニック
Course Schedule	★★	高	Topological Sorting（トポロジカルソート）
Course Schedule II	★★★	高	Topological Sorting（トポロジカルソート）
Find Eventual Safe States	★★★★	中	Topological Sorting（トポロジカルソート）

Topological Sorting（トポロジカルソート）

トポロジカルソートはダイクストラ同様基礎編においていますが、初見ではかなり難しい内容を扱います。しかし、こちらも非常に有名なアルゴリズムで、様々な問題に応用できますので必ずマスターしましょう。

トポロジカルソートを説明する前にDAGというグラフについて説明します。DAGとはDirected Acyclic Graphの略で、日本語で言うと有向非巡回グラフのことです。有向とは文字通り向きがあるグラフです。この非巡回とは閉路が存在しないことを指します。例えば以下の２つのグラフでは、左は有向で巡回（閉路）が無いのでDAGです。しかし右は巡回（閉路）が存在するためDAGではありません。