知识卡片
MST收缩要保留原边身份
MST-REDUCE 用并查集把已选轻边连接的顶点收缩成新顶点;跨新顶点的平行边只留最低代价边,同时记录 orig 指向原图边,以便将收缩图的 MST 还原。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 0 / 10 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 第21章 最小生成树 · 查看原书依据
11 G′.V = {FIND-SET(v) : v ∈ G.V} 12 G′.E = Ø 13 for each edge (x, y) ∈ G.E 14 u = FIND-SET(x) 15 v = FIND-SET(y) 16 if u ≠ v 17 if (u, v) ∉ G′.E 18 G′.E = G′.E ∪ {(u, v)} 19 (u, v).orig′ = (x, y).orig 20 (u, v).c′ = (x, y).c 21 elseif (x, y).c < (u, v).c′ 22 (u, v).orig′ = (x, y).orig 23 (u, v).c′ = (x, y).c 24 construct adjacency lists G′.Adj for G′ 25 return G′ and T
参考来源
- 位置:《算法导论(第4版)》第21章《最小生成树》(OEBPS/chapter021.xhtml,文本字符[30000,35000))。
- 结论依据:问题21-2的MST-REDUCE第11–25行完整给出收缩顶点、对平行边保留低权边,并在第19/22行保存原图边的orig映射;正确性还列作问题21-2(a)证明。
- 原始内容:11 G ′. V = {F IND -S ET ( v ) : v ∈ G.V } 12 G ′. E = Ø 13 for each edge ( x , y ) ∈ G.E 14 u = F IND -S ET ( x ) 15 v = F IND -S ET ( y ) 16 if u ≠ v 17 if ( u , v ) ∉ G ′. E 18 G ′. E = G ′. E ∪ {(u, v)} 19 ( u, v ). orig ′ = ( x , y ). orig 20 ( u , v ). c ′ = ( x , y ). c 21 elseif ( x , y ). c < ( u , v ).c′ 22 ( u , v ). orig ′ = ( x , y ). orig 23 ( u , v ). c ′ = ( x , y ). c 24 construct adjacency lists G ′. Adj for G ′ 25 return G ′ and T