最小生成树（Prim算法与Kruskal算法）

一、什么是最小生成树

一个连通图的生成树是一个极小的连通子图，它含有图中全部的n个顶点，但只有足以构成一棵树的n－1条边。我们把构造连通网的最小代价生成树称为最小生成树。

例如下图中①、②、③都是左侧图的生成树，但③是构造连通网的最小代价，所以③是该图的最小生成树。

二、Prim算法

Prim算法的核心思想如下：

• ① 将图中所有顶点分为A、B两类，初始时所有顶点都在B类
• ② 选择任意一个顶点，将其放入A类
• ③ 从B类所有顶点出发，找一条连接A类某个顶点且权值最小的边。将这条边连接的B类中的顶点放入A类中。
• ④ 重复③步骤，直到所有B类中的顶点全部放入A类。

下面通过图来说明最小生成树的构建过程

首先，在初始时，所有顶点都在B类

选择顶点A放入A类中，然后寻找B类到A类权值最小的边。很显然是BA这条边

将顶点B放入A类中，然后继续寻找B类到A类权值最小的边。结果是AE

将顶点E放入A类中，继续寻找。结果是AC

将顶点C放入A类中，继续寻找。结果只有BD

将顶点D加入A类，构建结束。

原理很简单，直接上代码。这里的图采用邻接矩阵存储

// 边结构
struct Edge:IComparable<Edge>
{
    public int from;
    public int to;
    public int weight;
    
    public int CompareTo(Edge other)
    {
        return weight - other.weight;
    }
}

private void Prim<T>(GraphByAdjacencyMatrix<T> graph)
{
	var graphCount = graph.Count;
	// 用来记录遍历过的顶点
	bool[] nodes = new bool[graphCount];
	// 用来记录当前遍历到的边
	Edge[] edges = new Edge[graphCount];

	// 将第一个顶点设置为已遍历
	nodes[0] = true;
	// 将第一个顶点对应的边加入集合
	// 都从1开始遍历是因为n个顶点对应n-1条边
	for (int i = 1; i < graphCount; i++)
	{
		edges[i] = new Edge {from = 0, to = i, weight = graph.Matrix[0, i]};
	}

	for (int i = 1; i < graphCount; i++)
	{
		// 找出权值最小的边
		int min = Int32.MaxValue;
		int minIndex = 0;
		for (int j = 1; j < graphCount; j++)
		{
			if (!nodes[j] && edges[j].weight < min)
			{
				min = edges[j].weight;
				minIndex = j;
			}
		}

		// 将新的顶点加入已遍历集合
		nodes[minIndex] = true;
		// 打印边
		Console.Write($"({edges[minIndex].from},{edges[minIndex].to}) ");

		// 将新的顶点对应的边加入集合
		// 忽略已经访问过的顶点、忽略比当前遍历的边更长的边
		for (int j = 1; j < graphCount; j++)
		{
			if (!nodes[j] && edges[j].weight > graph.Matrix[minIndex, j])
			{
				edges[j] = new Edge {from = minIndex, to = j, weight = graph.Matrix[minIndex, j]};
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

Prim算法关注的是顶点，通过寻找各顶点上权值最小的边，逐步构建起最小生成树。Prim算法的时间复杂度为$O(n^2)$，n为顶点数。因此对于边数非常多的稠密图，Prim算法在性能上会更有优势。

三、Kruskal算法

与Prim算法关注顶点的思路不同，Kruskal算法关注点在于边。它的原理也很简单，就是先将所有的边按权值从小到大进行排序。然后遍历边集，只要遍历到的这条边不会与结果集中的边形成环，就将其加入结果集。

代码如下

private void Kruskal<T>(GraphByAdjacencyMatrix<T> graph)
{
	// 自己实现的小根堆,用来对边排序
	HeapList<Edge> edges = new HeapList<Edge>();
	// 一维数组用来检验是否成环
	int[] parent = new int[graph.Count];
	
	// 将边加入小根堆
	for (int i = 0; i < graph.Count; i++)
	{
		for (int j = i+1; j < graph.Count; j++)
		{
			if(graph.Matrix[i,j] == Int32.MaxValue) continue;
			edges.Push(new Edge(){from = i,to=j,weight = graph.Matrix[i,j]});
		}
	}

	for (int i = 0; i < graph.Count; i++)
	{
		// 弹出权值最小的边
		var edge = edges.Pop();
		int m = Find(parent, edge.from);
		int n = Find(parent, edge.to);
		
		// 如果n!=m,则未形成环路
		if (n != m)
		{
			parent[m] = n;
			// 打印边
			Console.Write($"({edge.from},{edge.to})");
		}
	}
}

/// 

/// 校验是否成环
/// 
private int Find(int[] parent,int index)
{
	while (parent[index] != 0)
	{
		index = parent[index];
	}
	return index;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

这里的parent[]的作用可能有些难以理解。事实上它相当于一个并查集，用来检验是否成环。我们通过前面的例子来具体说明

首先进行校验的边是$(1,2)$，此时parent[]中的元素都为0，因此返回的m = 1,n = 2，因为m != n，所以将parent[1] = 2。这步操作意味着将顶点B（下标为1）和C（下标为2）加入了集合，且集合的代表为C

接下来进行校验的边是$(0,1)$。返回的m = 0,n = 2，所以将parent[0] = 2。即顶点A（下标为0）加入C这个集合

下一条边为$(0,4)$，返回的m = 2,n = 4，所以将parent[2] = 4。即将C集合整个加入E所在的集合

接下来是$(0,2)$，返回的m = 4,n = 4。此时n == m，意味着两个节点所在的集合都为E集合。也就是说这两个节点本身就是连通的，所以添加这条新的边会使生成树成环，需要舍弃。

接下来是$(1,3)$，返回的m = 4,n = 3，所以将parent[4] = 3，即将E集合加入D所在的集合

生成树构建完成，退出循环。

当图的边数为$e$时，Find()函数的时间复杂度为$loge$，外层循环的时间复杂度为$e$。因此整个算法的时间复杂度为$eloge$。Kruskal算法对于边数较少的稀疏图在性能上有很大优势。

四、参考资料

[1].《大话数据结构》
[2]. http://c.biancheng.net/algorithm/prim.html