知识卡片

普通读书笔记卡 · 3644.e

稀疏图可先收缩轻边

理解等级:中级

MST-REDUCE 对每个尚未配对顶点选一条最低权关联边,收进待构树,再把选中边连成的顶点集合收缩。

收缩后的平行边只留最低权者,并保留原边映射供还原。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 第21章 最小生成树 · 查看原书依据

      for each vertex u, choose the minimum-weight edge (u, v) incident on u, and put (u, v) into the minimum spanning tree under construction. Then, contract all chosen edges (see Section B.4). Rather than contracting these

    参考来源

    - 位置:《算法导论(第4版)》第21章《最小生成树》(OEBPS/chapter021.xhtml,文本字符[25000,30000))。 - 结论依据:问题21-2描述轻边选择、收缩、平行边最小权合并和 orig 映射;完整伪代码跨下一单元。 - 原始内容:for each vertex u , choose the minimum-weight edge ( u , v ) incident on u , and put ( u , v ) into the minimum spanning tree under construction. Then, contract all chosen edges (see Section B.4 ). Rather than contracting these