この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。
例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
3
各辺の重みはすべて1とします。最初に頂点1を選び、marked[1]=Trueとします。
次に、頂点1に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 2), (1, 3)
次に、キューから最小の重みの辺を取り出し、それに接続されている頂点2をマークします。
頂点2に隣接する辺をキューに追加します。
この時点でキューの状態は以下のようになります。
(1, 3), (1, 1), (1, 3)
ここで、次にキューから取り出す辺が(1, 1)であることに注意してください。
ただし、頂点1はすでにマークされているため、この辺を使ってしまうと、最小全域木の条件を満たさなくなります。
これが、以下のコード部分が必要とされる理由です。
if marked[i]:
continue
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。
探検
ニュース
- 【無言】中国怒らせた高市首相→1週間だんまり、国民に実害も説明なし 中国問題を避けてスルー… ★4 [BFU★]
- 【いちご高騰】ヤマザキのクリスマスケーキ、いちご無し販売 [おっさん友の会★]
- 【日中対立】 朝日新聞のタイトル修正が中国逆ギレの火種か SNSで批判相次ぐ [♪♪♪★]
- ネット殺到「高市総理の責任」「完全に高市リスク」「負けるな」中国が水産物輸入停止→流石に総理批判の声も「どう責任取る?」 ★10 [樽悶★]
- 「ドラゴンボール」初の全世界キャラクター人気投票が開幕!212キャラからナンバーワンが決まる!! [ひかり★]
- 【音楽】『日本レコード大賞』各賞発表! 大賞候補にILLIT、M!LK、ふるっぱー、幾田りら、アイナ、ミセスら… 作詩賞は指原莉乃 [冬月記者★]
- 中国、レアアース輸出制限wwwwwwwwwwwwwwwwwwwwwwww🎌 [329329848]
- おまえらって冷笑系おおすぎじゃね
- 日本をドーム状に覆って気温を一定にしたほうが過ごしやすいんじゃないの?
- 職場の人の雑談あまりにもどうでもよくて混ざらないんだけどさ
- 【すべてが】𝗮𝗺͜𝗮͉𝘇𝗼𝗻ブラックフライデーSALE総合【いいだろ!】 [194819832]
- オーバーオール毎日着てるけどどんなイメージ?
