有向グラフ

アルゴリズム

最小コストの閉路：

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

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

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

閉路のないDAG

問題へのリンク

問題概要

N人の選手がいる。各選手は１日１試合のみできる。総当たり戦を行う時、最短で何日かかるか？

ただし、i 番目の選手は \(A_{i, 1}, A_{i, 2}, \ldots, A_{i, ...

グラフとは

頂点(ノード)と、頂点同士の関係を表したデータ構造です。

数学的には、グラフは以下の２つから構成されます。

頂点（ノード）の集合
頂点同士がつながっているか(隣接しているか)を表す、辺（エッジ）の集合 ...