知识卡片

普通读书笔记卡 · 3644.c.3

MST增长过程形成森林

理解等级:中级

泛化 MST 的 A 始终是某棵树的子集,因此无环;(V,A) 是森林。每条安全边连接两个不同分量,分量数减一,故最多加入 |V|−1 条边。

这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

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

      At any point in the execution, the graph GA = (V, A) is a forest, and each of the connected components of GA is a tree. (Some of the trees may contain just one vertex, as is the case, for example, when the method begins: A is empty

    参考来源

    - 位置:《算法导论(第4版)》第21章《最小生成树》(OEBPS/chapter021.xhtml,文本字符[5000,10000))。 - 结论依据:原文从 A 是最优树子集推出森林性质,并解释每轮合并两个分量。 - 原始内容:At any point in the execution, the graph G A = ( V , A ) is a forest, and each of the connected components of G A is a tree. (Some of the trees may contain just one vertex, as is the case, for example, when the method begins: A is empty