グラフ

graph.png

トポロジカルソート
すべてのエッジの向きが右向きになるようにノードを並び替えること。
並び替えられる条件
閉路がない

閉路とは、環になっているというか、同じ頂点を何回も行ったりきたりしてしまうような場所のこと。

閉路がない、かつ有向グラフであるグラフをDAGと呼ぶ。
DAGとはDirected Acyclic Graph の略で日本語でいうと無閉路有向グラフである。

DAGであればダイクストラ法やメモ化再起で解くことができる。

サポートサイト Wikidot.com