競技プログラミング総合スレ 66 (478ﾚｽ)
上下前次1-新
抽出解除 必死ﾁｪｯｶｰ(本家) (べ) 自ID ﾚｽ栞 あぼーん
171(2): (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:19 ID:fcL4nlHr0(1/3) AAS
この部分は、既にマークされた頂点に対応する辺をスキップするために必要です。
確かに、キューには基本的にmarkedの値がFalseのノードしか入らないように見えますが、
実際には同じノードに対して複数の辺がキューに入ることがあります。
例えば、次のようなグラフを考えてみましょう。
1 -- 2
| /
| /
省16
174: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:28 ID:fcL4nlHr0(2/3) AAS
>>172
確かに、ヒープにプッシュする前にそのノードがマークされていないことをチェックしています。
ただし、ヒープにプッシュされた後で、そのノードが他の辺を経由してマークされる可能性があります。
そのため、ヒープから辺を取り出す前にもう一度マークされているかどうかをチェックする必要があります。
先程のグラフで考えてみましょう。キューがこの様になったところから解説します。
(1, 3), (1, 1), (1, 3)
ここで、最初に(1, 3)をキューから取り出し、頂点3をマークします。この時点で、キューには以下のような状態が残っています。
省5
176: (ﾜｯﾁｮｲ 412d-dXWb) 2023/04/09(日)18:31 ID:fcL4nlHr0(3/3) AAS
>>175
はい、その通りです。
最初にノード1からノード3への辺がヒープに追加され、次にノード2からノード3への辺がヒープに追加されます。
(1, 3) <-- 1から3への辺
(1, 1)
(1, 3) <-- 2から3への辺
このように、同じノードが複数回ヒープに入ることがあります。プリムのアルゴリズムでは、
省2
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.649s*