Microsoft PowerPoint - ad09-09.pptアルゴリズムと データ構造 ６．２．１節：最小木 ２．５節：集合族の併合 塩浦昭義 情報科学研究科 准教授 shioura@dais.is.tohoku.ac.jp 今日の講義の概要 グラフのデータ構造 最小木問題 最小木を求める２つのアルゴリズム クラスカルのアルゴリズム アルゴリズムの計算時間の解析 集合族の併合のためのデータ構造 無向グラフ G=(V, E) 頂点集合 V 頂点の対を表す枝の集合 E e=(u,v) 頂点 u, v は枝 e の端点 無向グラフと有向グラフ 2 3 0 1 4 a c f e d b 2 3 0 1 4 a c f e d b 有向グラフ G=(V, E) 頂点集合 V 頂点の順序対を表す枝の集合 E e=(u,v)頂点uは枝eの始点 頂点vは枝eの終点 グラフ G=(V, E) を表現す
