DOSEI https://blog.hatena.ne.jp/DOSEI/ DOSEIの日記 https://dosei.hatenadiary.jp/ 講義 グラフとネットワーク 講義 グラフとネットワーク ○最小重み全域木を求めるアルゴリズム（クルスカルのアルゴリズム） 最小の重みの辺を登録 まだ登録されていない辺から、サイクルにならないような最小の重みを登録 全域木でなければ、2へ このような各段階で最適なものを選ぶ方法を貧欲法(Greedy Algorithm)という。 サイクルになるかどうかの判定方法。 両端が無印なら、新しい番号の同じラベルを両側につける。 片側のみラベルがある場合は、同じラベルをもう一方につける。 両端が異なる場合は、どちらか一方のラベル群をもう一方に書き換える。同じ時はサイクルになるので× ○グラフの頂点探索 深さ優先探索⇒スタックを使う 幅優先探索⇒キューを使う ○… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fdosei.hatenadiary.jp%2Fentry%2F20031219%2Fp4" title=" - DOSEIの日記" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2003-12-19 00:00:03 rich https://dosei.hatenadiary.jp/entry/20031219/p4 1.0 100%