除了最短路径[shortest path]问题，图的另一个经典问题是最小生成树。给定一个图[一般是无向图]，有n个点及一些连接的边每个边上都有对应的权重[权重可以用来描述任何可以量化的因素]，现在我们想要寻找一个子图能够将所有的点都链接起来[也就是说在这个子图内，任何两个节点可以直接或者间接连通]，并且要求子图的权重最小。这个子图就是所谓的最小生成树，或者更准确的说最小权重生成数[最小生成树不是惟一的，一个图可能有多个不同的最小生成树，比如两条边的权重一样，选择任何一条都可以形成最小生成树]。

最小生成树最出名的方法，就是Prime算法和Kruskal算法。

Prime 算法

Prime算法的主要思想是不断选择相邻权重最小的边直到所有节点连通，具体步骤：

  1. 确定源点，将源点加入确定点集，剩下的所有点放入待确定点集[可以选择最短路径的其中一个点作为源点]。
  2. 从所有与确定点集中的点相邻节点的边中选择权重最小的边，并将此边连接的节点加入确定点集，从不确定点集删除此点。
  3. 直到不确定点集为空，算法结束，所得到结果就是最小生成树。

一个简单的Prime算法实例及说明

Prime Algorithm

Kruskal 算法

Kruskal算法的主要思想是将所有边按照权重排列，每次选择最短的边[但不考虑已经被其他边连通的两个点所组成的边，即便它的权重小]，直至所有节点都连通。

一个简单的Kruskal算法实例及说明:

Kruskal Algorithm

另外一个算法步骤描述是[等价于前面一个的描述]：

  1. 将所有的边按权重排序
  2. 从最小权重的边开始依次加入确定边集合，并保证加入该边不会形成环
  3. 直到所有的点都被覆盖。

本文部分内容源自互联网