この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的に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
この部分によって、既にマークされた頂点に対応する辺をスキップし、
正しい最小全域木を構築することができます。
探検
ニュース
- 高市首相の答弁書に「台湾有事答えない」と明記 存立危機発言当時 ★3 [蚤の市★]
- 「偽サッチャー」「自滅的」「時代遅れ」 高市首相の経済政策を海外メディアが酷評 ★2 [蚤の市★]
- 「もうキモくてキモくて…」29歳女性が語る“おぢアタック”の実態。「俺ならイケるかも」年下女性を狙う勘違い中年男性に共通点が★5 [Hitzeschleier★]
- 東京都「都民の税金1.5兆円が国に奪われている」「全国に分配されている」に地方民ブチギレ ★2 [Hitzeschleier★]
- 【ド軍】山本由伸、WBC出場を決断!ドジャースが本人の意向を尊重、佐々木朗希はチームが故障歴を懸念で不参加 [鉄チーズ烏★]
- 米大統領報道官「日本と強固な同盟維持、中国とも協力」 [少考さん★]
- 【高市悲報】トケドロ高橋「あれまw日本は食料品だけ上がっていてインフレとは言えない😤円安上等!」 [359965264]
- 竹中平蔵「日米が長年守り続けてき台湾有事に関する曖昧戦略の知恵を一瞬にして無にさせた岡田の責任は非常に重い」 [271912485]
- 中国人、超ド正論。「チベットやウイグルに住んでるのはチベット族やウイグル族だが、アイヌから奪った土地に住んでる日本人こそ侵略者」 [314039747]
- 【画像】海外の寿司パーティー、レベチwwwwwwwwww [834922174]
- マクドナルド、超えてはいけないラインを超えるwwwwwwwwwwwwwwwwwwwww [977790669]
- 【悲報】銀価格、ついに1g350円突破!ガチのマジで大暴騰開始wwwwwwwwwwwwwwwwwwww [802034645]
