Day 23：最小生成树(MST)

贪婪演算法可以解决的一个问题就是找到一张图中的最小生成树(minimum spanning tree)。

树、生成树与最小生成树

我们之前提到资料结构中的树是有根树(rooted tree)，也就是树中有一个根节点。但其实树不一定都有根节点，只要任意两节点都有(也只有)一条边相连的图就称作树。

图片来源：维基百科

而一个图中的生成树(spanning tree)，就是指连接该图所有节点的树，一个图可能有不只一个生成树。而最小生成树就是指在有权图中，权重总和最小的生成树。例如下图中绿色的部分，就是这个图的最小生成树。

图片来源：维基百科

那麽最小生成树可以解决什麽问题呢？其中一种最直接的应用是线路设计，例如沿着街道(边)为住家(节点)架设电缆的情境，最小生成树可以作为成本最低的路径。另外，最小生成树也可以用来作为困难问题的近似解，或间接应用在人脸或字迹辨识等技术中。

贪婪解法

有许多演算法可以找到一个图中的最小生成树，下面写到的几种都是属於贪婪演算法。这几种方法虽然关注点或出发点不同，但同样都是用贪婪策略，每一阶段都选择局部最佳解，以达到最终的整体最佳解。也表现出之前提到的，一个问题可能以多种贪婪演算法解决。

Prim's algorithm

普林演算法的策略与先前提到寻找最短路径的Dijkstra演算法非常相似(事实上这个演算法也被Dijkstra再次发现与发表，所以也称为Prim–Dijkstra algorithm)，它的作法是：

1. 先将任意节点加入到树之中。

2. 选择与树距离最近的节点，加入到树中，反覆此步骤直到所有节点均在树中，即为最小生成树。

以上方的图为例，如果一开始选择G节点，接下来将最近的节点E加入树中，接下来将与G或E最近的节点C加入...以此类推，也就是每一阶段树都会纳入距离最近的节点、增加一条边，直到连接所有的节点。

Kruskal's algorithm

Kruskal演算法的方式是从所有边中，反覆选择最短的边，它的步骤是：

1. 将所有的边依照权重由小到大排序。

2. 从最小开始，选择不会形成环的边，直到连接所有节点。

如下图，先将边排序，依序选择，其中边be即是因为会形成环所以不选。

图片来源：维基百科

Borůvka's algorithm

Borůvka演算法则是利用节点的最短边得出多棵树，再将树以最短边相连：

1. 找寻每个节点的最短边，可以重复选择(例如下图AC同时是A节点和C节点的最短边)，如此一来会形成几个不相连的树，如下图中经过第一步骤後得到AC、BD、EF等不同的树，以不同颜色标示。
2. 以同样的方式，反覆找寻每个树的最短边，每次操作树的数量都会减少，直到最终只剩下一个树即为最小生成树。

图片来源：维基百科