15、图算法：最小生成树与节点着色

图算法：最小生成树与节点着色

1. 最小生成树（MST）简介

在图论中，生成树是一个很重要的概念。生成树是图中连接所有节点且无环的边的子集。同一个图中可能存在多个生成树。例如，有一个图，左边的生成树由边(1, 2)、(1, 3)、(3, 4)、(4, 5)、(5, 6)、(6, 7)和(5, 8)组成，总权重为40；右边的生成树由边(1, 2)、(1, 3)、(2, 4)、(4, 8)、(5, 8)、(5, 6)和(6, 7)组成，总权重为31。

然而，这两个生成树都不是该图的最小生成树（MST）。最小生成树是指图中所有生成树中成本最小的那个。在这个例子中，将边(6, 7)替换为(5, 7)，就能得到MST，此时成本为30。需要注意的是，生成树的边数等于节点数减1。

最小生成树在现实生活中有很多应用。比如，要将许多建筑物连接到通信电缆上，可能有多种连接方式，而且环境条件（如穿越道路或河流）会严重影响投资成本。这时，我们可以创建一个图，节点代表连接器，边表示可能的连接，然后找出MST，就能以最低成本成功连接所有建筑物。

2. 寻找最小生成树的算法

2.1 Kruskal算法

Kruskal算法的操作很简单。该算法从剩余边中选取权重最小的边，只要添加这条边不会形成环，就将其加入MST，直到所有节点都被连接。

以下是使用Kruskal算法寻找MST的步骤：
1. 第一步，选择边(5, 8)，因为它的权重最小，为1。
2. 接着依次选择边(1, 2)、(2, 4)、(5, 6)、(1, 3)、(5, 7)。
3. 在选择边(4, 8)之前，考虑过边(6, 7)，因为它权重