2003-12-19 ■ 講義 グラフとネットワーク 講義 グラフとネットワーク ○最小重み全域木を求めるアルゴリズム(クルスカルのアルゴリズム) 最小の重みの辺を登録 まだ登録されていない辺から、サイクルにならないような最小の重みを登録 全域木でなければ、2へ このような各段階で最適なものを選ぶ方法を貧欲法(Greedy Algorithm)という。 サイクルになるかどうかの判定方法。 両端が無印なら、新しい番号の同じラベルを両側につける。 片側のみラベルがある場合は、同じラベルをもう一方につける。 両端が異なる場合は、どちらか一方のラベル群をもう一方に書き換える。同じ時はサイクルになるので× ○グラフの頂点探索 深さ優先探索⇒スタックを使う 幅優先探索⇒キューを使う ○最短経路問題 ダイクストラ法…適当