この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的に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
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。
ニュース
- “ひとり焼肉”でおなじみ「焼肉ライク」が閉店ラッシュ。なぜ「コスパが悪い」と言われてしまうのか [Gecko★]
- なぜリベラルは人気がないのか 斎藤幸平さんが指し示す未来への道筋:朝日新聞 [少考さん★]
- 女性天皇「賛成」69%、将来の皇位継承「不安」68%…読売世論調査 [蚤の市★]
- 【日中】経団連会長、1月の北京訪問に暗雲 中国は受け入れ是非明らかにせず 関係「政冷経冷」に [煮卵★]
- 中国の渡航自粛要請1カ月 大阪の観光バス予約ゼロ、東北にも波及 [蚤の市★]
- 女性のハイヒールが消滅の危機!「今いる職人がいなくなったら終わってしまう」老舗メーカー、歌姫の引退が痛手とも [牛丼★]
- 【高市朗報】鈴木大臣「嫌儲のデマに騙されないで。お米券の使い勝手は悪くない。卵味噌醤油も買えます。現金と変わりません」 [517459952]
- 政治家、気づく「ヤードとかいう単なる犯罪拠点、規制したほうがよくないか?」 [792147417]
- 🏡おい!返事しろ︎︎!知的障害者!
- 高市、メガソーラー廃止。環境破壊が社会問題化 [792147417]
- きょうはおさけのんでいいひだけど
- なぜ、ネトウヨは例外なく狂っているのか? [805596214]
