最小生成树
最小生成树以最小的总边权重连接加权连通图的所有顶点；Kruskal算法和Prim算法等贪婪算法可以有效地计算出最小生成树。
用 PaperMind 寻找选题即将推出Find papers & topics
Tools & resources
Learn & explore
视频即将推出
Definition
连通的、边加权图的最小生成树是边的子集，它连接所有顶点，不包含环，并且在所有此类生成树中具有最小的总权重。
Scope
本主题涵盖了最小生成树问题及其经典的贪婪解法——Kruskal算法（使用不相交集结构按权重递增顺序添加边）和Prim算法（使用优先队列生长单个树），以及证明这些算法正确性的割性质和环性质。它还涉及支持性的不相交集（并查集）数据结构。
Core questions
- 什么是生成树，以及什么使其具有最小权重？
- 为什么贪婪的边添加会产生全局最小生成树？
- 割性质和环性质如何证明MST算法的正确性？
- Kruskal算法和Prim算法在策略和数据结构上有何不同？
- 不相交集（并查集）结构如何使Kruskal算法高效？
Key concepts
- 生成树
- 割性质
- 环性质
- Kruskal算法
- Prim算法
- 不相交集（并查集）
- 贪婪安全边
- 边权重
Key theories
- 割性质
- 对于将顶点划分为两个集合的任何划分，跨越该划分的最小权重边属于某个最小生成树；这种安全边保证是Kruskal算法和Prim算法这两种贪婪算法正确性的基础。
- 不相交集并查集支持
- Kruskal算法使用带有按秩合并和路径压缩的并查集结构，以接近常数的均摊时间测试添加边是否会创建环。
Clinical relevance
最小生成树模拟了成本最低的网络设计：铺设连接所有站点的廉价通信、电力或交通网络。它们还在聚类、图像分割、旅行商问题的近似算法以及点集分析中作为构建块。
History
最小生成树问题最早由Otakar Borůvka于1926年为电力网络设计而解决。Vojtěch Jarník（1930年）以及后来的Prim（1957年）和Dijkstra发展了树生长方法，而Kruskal（1956年）提出了边排序的贪婪方法，使其成为最早被充分理解的组合优化问题之一。
Key figures
- Joseph Kruskal
- Robert Prim
- Otakar Borůvka
- Vojtěch Jarník
Related topics
Seminal works
- kruskal1956
- cormen2009
Frequently asked questions
- Kruskal算法和Prim算法有什么区别？
- Kruskal算法对所有边进行排序，并按权重递增的顺序添加它们，跳过任何会形成环的边，并使用并查集来检测环。Prim算法从一个起始顶点开始生长一棵连通树，重复添加离开当前树的最便宜的边，并使用优先队列。两者都产生一个最小生成树。
- 最小生成树是唯一的吗？
- 如果所有边的权重都不同，则最小生成树是唯一的。当某些权重相等时，可能存在几个不同的最小生成树，所有这些树都具有相同的最小总权重。