最小生成树

在阅读下列内容之前，请了解 图 和 树 相关内容，并了解以下定义：

1. 生成子图
2. 生成树

定义

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

Kruskal 算法

Kruskal 算法是一种常见并且好写的最小生成树算法，由 Kruskal 发明。该算法的基本思想是从小到大加入边，是个贪心算法。

前置知识

并查集、贪心、图的存储。

实现

伪代码：（不写正经代码是因为不想写并查集……真想看去找AI吧~）

$$\begin{array}{ll} 1 & \textbf{Input. } \text{The edges of the graph } e , \text{ where each element in } e \text{ is } (u, v, w) \\ & \text{ denoting that there is an edge between } u \text{ and } v \text{ weighted } w . \\ 2 & \textbf{Output. } \text{The edges of the MST of the input graph}.\\ 3 & \textbf{Method. } \\ 4 & result \gets \varnothing \\ 5 & \text{sort } e \text{ into nondecreasing order by weight } w \\ 6 & \textbf{for} \text{ each } (u, v, w) \text{ in the sorted } e \\ 7 & \qquad \textbf{if } u \text{ and } v \text{ are not connected in the union-find set } \\ 8 & \qquad\qquad \text{connect } u \text{ and } v \text{ in the union-find set} \\ 9 & \qquad\qquad result \gets result\;\bigcup\ \{(u, v, w)\} \\ 10 & \textbf{return } result \end{array}$$

算法虽简单，但需要相应的数据结构来支持……

具体来说，维护一个森林，查询两个结点是否在同一棵树中，连接两棵树。

抽象一点地说，维护一堆 集合，查询两个元素是否属于同一集合，合并两个集合。

其中，查询两点是否连通和连接两点可以使用并查集维护。

如果使用 O(mlogm) 的排序算法，并且使用 O(mα(m, n)) 或 O(mlogn) 的并查集，就可以得到时间复杂度为 O(mlogm) 的 Kruskal 算法。

证明

思路很简单，为了造出一棵最小生成树，我们从最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就扔掉这条边，直到加入了 n-1 条边，即形成了一棵树。

证明：使用归纳法，证明任何时候 K 算法选择的边集都被某棵 MST 所包含。

基础：对于算法刚开始时，显然成立（最小生成树存在）。

归纳：假设某时刻成立，当前边集为 F，令 T 为这棵 MST，考虑下一条加入的边 e。

如果 e 属于 T，那么成立。

否则，T+e 一定存在一个环，考虑这个环上不属于 F 的另一条边 f（一定只有一条）。

首先，f 的权值一定不会比 e 小，不然 f 会在 e 之前被选取。

然后，f 的权值一定不会比 e 大，不然 T+e-f 就是一棵比 T 还优的生成树了。

所以，T+e-f 包含了 F，并且也是一棵最小生成树，归纳成立。

Prim 算法

Prim 算法是另一种常见并且好写的最小生成树算法。该算法的基本思想是从一个结点开始，不断加点（而不是 Kruskal 算法的加边）。

实现

代码

import sys

class Graph:
    # 初始化图
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for _ in range(vertices)] for _ in range(vertices)]

    # 加边
    def add_edge(self, u, v, weight):
        self.graph[u][v] = weight
        self.graph[v][u] = weight

    # 找最短边
    def min_key(self, key, mst_set):
        min_value = sys.maxsize
        min_index = -1
        for v in range(self.V):
            if key[v] < min_value and not mst_set[v]:
                min_value = key[v]
                min_index = v
        return min_index

    def prim_mst(self):
        parent = [-1] * self.V				# 最小边的父节点，用来储存mst
        key = [sys.maxsize] * self.V		# 初始化距离无穷远
        key[0] = 0							# 源点置0
        mst_set = [False] * self.V			# 访问标志初始化

        for _ in range(self.V):
            u = self.min_key(key, mst_set)	# 寻找最短边
            mst_set[u] = True				# 将其归入已生成集

            # 更新最小生成树
            for v in range(self.V):
                if self.graph[u][v] > 0 and not mst_set[v] and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        return parent

    

# 建图
g = Graph(5)
g.add_edge(0, 1, 2)
g.add_edge(0, 3, 6)
g.add_edge(1, 2, 3)
g.add_edge(1, 3, 8)
g.add_edge(1, 4, 5)
g.add_edge(2, 4, 7)
g.add_edge(3, 4, 9)

parent = g.prim_mst()

print("边   权")
for i in range(1, g.V):
    print(f"{parent[i]} - {i}    {g.graph[i][parent[i]]}")

运行结果

边   	权
0 - 1    2
1 - 2    3
0 - 3    6
1 - 4    5

正确性

从任意一个结点开始，将结点分成两类：已加入的，未加入的。

每次从未加入的结点中，找一个与已加入的结点之间边权最小值最小的结点。

然后将这个结点加入，并连上那条边权最小的边。

重复 n-1 次即可。

证明：还是说明在每一步，都存在一棵最小生成树包含已选边集。

基础：只有一个结点的时候，显然成立。

归纳：如果某一步成立，当前边集为 F，属于 T 这棵 MST，接下来要加入边 e。

如果 e 属于 T，那么成立。

否则考虑 T+e 中环上另一条可以加入当前边集的边 f。

首先，f 的权值一定不小于 e 的权值，否则就会选择 f 而不是 e 了。

然后，f 的权值一定不大于 e 的权值，否则 T+e-f 就是一棵更小的生成树了。

因此，e 和 f 的权值相等，T+e-f 也是一棵最小生成树，且包含了 F。

复杂度

寻找最短边时，需要遍历所有未包括在最小生成树集合中且权重最小的顶点，时间复杂度为O(V)；选择最小边时，需要遍历所有顶点，时间复杂度也为O(V)。总共有V次选择最小边的操作，因此总时间复杂度为O(V^2)。

父节点数组parent、顶点到最小生成树的最小权重数组key和最小生成树集合标记数组mst_set的空间复杂度都为O(V)，没有使用额外的数据结构，所以总空间复杂度为O(V)。