[算法系列之二十七]Kruskal最小生成树算法

简介

求最小生成树一共有两种算法，一个是就是本文所说的Kruskal算法，另一个就是Prime算法。在详细讲解Kruskal最小生成树算法之前，让我们先回顾一下什么是最小生成树。

我们有一个带权值的图，我们要求找到一个所有生成树中具有最小权值的生成树。如下图所示，T是图G的生成树。但不是具有最小权值的生成树。

我们可以把他们想象成一组岛屿和连接它们的可能的桥梁。当然修桥是非常昂贵和费时的，所以我们必须要知道建设什么样的桥梁去连接各个岛。不过有一个重要的问题，建设这样一组连接所有岛屿的桥梁的最低价格是多少。

我们实际上需要构建一棵最小生成树，，顶点表示岛屿，而边表示它们之间可能要修建的桥梁。每一个可能修建的桥梁都有相应的权值（表示我们建造它所花费的时间和金钱等）。

在实践中，我们只可能使用一个最小生成树的可能用例。（This scenario is only one of possible use cases of where minimum spanning trees can be used in practice.）

概要

Kruskal算法开始由初始化一组集合，并建立| V|棵树，每棵树都只包含了图的一个顶点。

在建设最后生成树的过程中，我们维护一个森林。很显然，我们由|V|棵树组成的森林开始，其中每个树都只有是一个节点。

在某些时候，我们有“K”棵树组成的森林，这几棵树都最小生成树的子树。

构建最终的最小生成树最后一个步骤之前，我们有两个树（如上图的3），我们用剩下的最小权值边来连接这两棵树。

构建树的过程中，我们按照权值的升序，对边进行排序。

然后，获取边，检查每条边（u，v），其端点u和v是否是属于同一棵树。如果是，把（u，v）加入森林中就会形成一个回路，所以放弃这条边（u，v）。否则，说明两个顶点分属不同的树。

关于Kruskal算法一个很大的特点是，它也可以用在非连同图中。

原文

Computer Algorithms: Kruskal’s Minimum Spanning Tree

你不怕困难，困难就怕你。