LeetCode 練習問題集
問題 | 難易度 | 重要度 | テクニック |
★★ | 高 | Topological Sorting（トポロジカルソート） | |
★★★ | 高 | Topological Sorting（トポロジカルソート） | |
★★★★ | 中 | Topological Sorting（トポロジカルソート） |
Topological Sorting（トポロジカルソート）
トポロジカルソートはダイクストラ同様基礎編においていますが、初見ではかなり難しい内容を扱います。しかし、こちらも非常に有名なアルゴリズムで、様々な問題に応用できますので必ずマスターしましょう。
トポロジカルソートを説明する前にDAGというグラフについて説明します。DAGとはDirected Acyclic Graphの略で、日本語で言うと有向非巡回グラフのことです。有向とは文字通り向きがあるグラフです。この非巡回とは閉路が存在しないことを指します。例えば以下の２つのグラフでは、左は有向で巡回（閉路）が無いのでDAGです。しかし右は巡回（閉路）が存在するためDAGではありません。
