BFS

アルゴリズム

最小コストの閉路：

任意の辺 e = (u,v) について以下を繰り返すグラフ G から e を取り除く
v から u への最短経路 d を求める(ダイクストラ/BFS など)
d+cost(u, ...

トポロジカルソートとは、閉路の無い有向グラフ DAG について行うソートです。

左図のDAGを右図のように頂点を一列に並べて、全ての辺の向きが左から右になるようにすることを言います。

閉路のないDAG

問題

木構造について、頂点から見た時に自身から伸びる枝に重複が無いように色を塗る。使う色の数の最小値はいくつか？

問題：D – Coloring Edges on Tree

(木構造はグラフの一種と捉 ...