知识卡片
MST增长过程形成森林
泛化 MST 的 A 始终是某棵树的子集,因此无环;(V,A) 是森林。每条安全边连接两个不同分量,分量数减一,故最多加入 |V|−1 条边。
这张卡片看不懂?
这张卡片的反馈已满 10 条,暂时无法继续提交。
已有反馈 · 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