最小生成树算法概览
原创约 729 字
最小生成树是图论中的经典问题，在现实生活中有广泛的应用，比如设计最低成本的通信网络、电路布线、管道铺设等。
考虑到最小生成树的算法实现需要一些其他算法作为铺垫，且本文处在基础章节，所以不会详细讲解算法代码。
本文主要介绍最小生成树的定义及应用场景，并阐述两种经典的最小生成树算法的核心原理。具体的代码实现安排在数据结构设计章节。
什么是生成树
首先理解什么是生成树。给定一个无向连通图 ，其生成树是 的一个子图，它包含 中的所有顶点，并且是一棵树（即无环连通图）。
换句话说，生成树具有以下特性：
- 包含原图中的所有顶点。
- 边的数量为顶点数减一（
V-1条边）。 - 连通且无环。
一个图可以有多个不同的生成树，例如这幅加权图：
可以有以下生成树，其中属于生成树的边被标记为了红色：
下面是一个不同的生成树：
什么是最小生成树
如果图是加权图，那么最小生成树就是边权重总和最小的生成树。
比如上面展示的例子，第二种生成树是该图的最小生成树，总权重为：2 + 3 + 5 = 10，没有其他的生成树能够得到更小的权重和了。
最小生成树在现实生活中有很多应用场景，边的权重可能代表距离、成本、时间等。
比方说想在若干城市之间修建公路，图中的节点代表城市，边代表城市之间的公路，边的权重代表修建公路的成本，我们希望找到一种方案能够连接所有城市，且总成本最小，这就是典型的最小生成树问题。
最小生成树算法
有两种经典的算法用于求解最小生成树问题：Kruskal 算法和 Prim 算法。它们都基于贪心思想，但实现方式不同。
Kruskal 算法相对简单一些，只需要先对图中的所有边按照权重排序，然后借助 Union-Find 并查集算法 即可找到最小生成树。
Prim 算法可以由 Dijkstra 算法 拓展而来，借助 优先级队列 动态排序的特性，逐步构造最小生成树。
具体的代码实现在 Kruskal 算法 和 Prim 算法 中讲解。