第7章グラフアルゴリズム

グラフの表現

• 隣接行列
• 接続リスト
• 隣接リスト

n+1頂点の根付き木とn頂点の2分木の頂点の集合は1対1に対応する。

ダイクストラのアルゴリズム

最短路木を作ってやれば、最短路を求めることができる
作り方：Uからuを取り出したときに、その親との関係を保持してゆけば最終的に木になる。