LeetCode 練習問題集
問題 | 難易度 | 重要度 | テクニック |
★★ | 高 | Topological Sorting(トポロジカルソート) | |
★★★ | 高 | Topological Sorting(トポロジカルソート) | |
★★★★ | 中 | Topological Sorting(トポロジカルソート) |
Topological Sorting(トポロジカルソート)
トポロジカルソートはダイクストラ同様基礎編においていますが、初見ではかなり難しい内容を扱います。しかし、こちらも非常に有名なアルゴリズムで、様々な問題に応用できますので必ずマスターしましょう。
トポロジカルソートを説明する前にDAGというグラフについて説明します。DAGとはDirected Acyclic Graphの略で、日本語で言うと有向非巡回グラフのことです。有向とは文字通り向きがあるグラフです。この非巡回とは閉路が存在しないことを指します。例えば以下の2つのグラフでは、左は有向で巡回(閉路)が無いのでDAGです。しかし右は巡回(閉路)が存在するためDAGではありません。
![notion image](https://www.notion.so/image/https%3A%2F%2Fstorage.interviewcat.dev%2Fcoding-interviewcat%2FGraph%2F4_basic-TopologicalSort%2FIntroduction%2FDAG_not_DAG_image.png?table=block&id=91b13a12-81c3-4eda-a1db-1da073c20002&cache=v2)