简介
最小生成树 (Minimum Spanning Tree) 应该大家都不陌生，当然还有最大生成树啦，这篇文章就简单总结一下算法里的生成树。
什么是生成树
Spanning 有跨越的意思，生成树一般来说每个节点都能访问到别的节点，是一个连通树。所以，一般考虑无向图里去造生成树。生成树又分最小和最大两种，其中最小生成树应用比较多。总结一下生成树的定义：
- 首先它得是一个树的结构
- 所有的节点都能互相访问
- 要么最小要么最大（废话）
如下图所示，加粗的黑边就是最小生成树。
特性
生成树有两个看起来很废话的特性 Cycle Property 和 Cut Property，这里以最小生成树为主来说明。
Cycle Property
如果在一个环里，其中某条边 e 是这里面的权重最大的边，那么这条边一定不在最小生成树里。
举个例子，上图我们看到其中一个环 0 -> 1 -> 7 -> 0，我们发现边 1 -> 7 是这里面权重最大的，那么就一定不会在这张图的最小生成树里。
Cut Property
再来看看 Cut Property，如果你把图里的节点分成两堆，里面最权重最小的边是一定会在这张图的最小生成树里的。
如下图所示，边 f 是权重最小的连接两堆节点的边，这条边一定在最小生成树里。
上面两个特性是不是感觉很废话？但是这是后面造最小生成树的基础。当然最大生成树取反就好了。
算法
下面说说通常找最小生成树的算法，这些算法都能使用上面生成树的两个特性来证明其正确性。
Kruskal
- 首先获取所有的边，都这些边进行从小到大的排序
- 然后不断往图里添加边，并且避免造成环
- 直到所有点都能互相访问后停止算法
伪代码如下：
function kruskal(graph) {
// 对图里的边进行排序
const sortedEdges = graph.edges.sort()
// 去掉图里的边
graph.removeAllEdges()
for (let i = 0; i < sortedEdges.length; i++) {
graph.addEdge(sortedEdges[i])
// 如果添加的边造成环，那么就移除
if (graph.hasCycle()) {
graph.removeEdges(sortedEdges[i])
}
}
return graph
}
例子如下
这个算法的时间复杂度是
Jarnik (Prim)
可能大家都知道 Prim，其实它还有一个名字是 Jarnik。算法步骤如下：
- 从一个节点（随便选一个）开始，去找这个节点相邻最短的边
- 将找到的边添加到这个节点上，这就形成一个组件了
- 再从这个组件开始去找相邻权重最小的边，再添加到这个组件上，不断重复直到所有节点都能被访问
伪代码如下：
function prim(graph) {
const visited = []
// 从一个节点开始
const sourceComponent = graph.randomVertex()
// 如果还有节点不能被访问就继续找
while (visited.length < graph.vertices.length) {
// 将相邻权重最小的边作为组件的一部分，且不构成环
const smallestEdge = sourceComponent.findSmallestEdge()
sourceComponent.addEdge(smallestEdge)
visited.push(smallestEdge.toVertex)
}
}
下面的例子就是使用 Prim 算法来找到最小生成树的。
这个算法的时间复杂度是
Boruvka
Boruvka 算法又叫作 Sollin 算法，它其实是 Prim 算法的变种，Prim 是从一个节点开始找最小边，而 Boruvka 是所有节点一起找最小边。具体步骤如下：
- 首先也是像上面一样去掉全部的边，每个节点都是一个组件（森林）
- 对于每个组件（森林）都找其相邻权重最小的边，将这些边添加到组件上，不断重复直到所有的节点都能被访问
- 这里对添加的边要做一个是否构成环的判断
伪代码如下：
function boruvka(graph) {
const visited = []
const components = graph.vertices
while (visited.length < graph.vertices.length) {
for (let i = 0; i < components.length; i++) {
// 找到相邻最小边
const smallestEdge = components[i].findSmallestEdge()
components[i].addEdge(smallestEdge)
visited.push(smallestEdge.toVertex)
// 合并某些组件
combine(components)
}
}
}
下面例子使用 Boruvka 来找最小生成树。
