一、最小生成树问题

1. 问题描述

• 设G =(V,E)是无向连通带权图，即一个网络。（V是顶点集合，E是边集合）
• 如果G的子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。生成树上各边权的总和称为该生成树的耗费。
• 在G的所有生成树中，耗费最小的生成树称为G的最小生成树。

2. 算法分析

• Prim算法和Kruskal算法：都是解最小生成树问题的贪心算法；它们做贪心选择的方式不同，但都利用了下面的最小生成树性质。

最小生成树性质：

• 设G=(V,E)是连通带权图，U是V的真子集。
• 如果(i,j)∈E，且i∈U，j∈V-U，且在所有这样的边中，(i,j)的权c[i][j]最小，那么必存在一棵包含边(i,j)的最小生成树。
• 这个性质也称为MST（Minimum Spanning Tree）性质。

2.1. Prim算法

• 贪心选择策略： 每次都选择到下一顶点权最小的边。

• 基本步骤：

  1. 置顶点集合S={1}；
  2. 只要S是V的真子集，就作如下的贪心选择：选取满足条件i∈S，j∈V-S，且c[i][j]最小的边，将顶点j添加到S中。
  3. 这个过程一直进行到S=V时为止，选取到的所有边恰好构成G的一棵最小生成树。

• 举个例子： 对于图1中的连通带权图，按Prim算法选取边的过程如图2。
  

2.2. Kruskal算法

• 贪心选择策略： 每次都选择权最小的可以连通两个不同连通分支的边。

• 基本步骤：

  1. 将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。
  2. 从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：
     • 当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；
     • 如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边；
  3. 这个过程一直进行到只剩下一个连通分支时为止，选取到的所有边恰好构成G的一棵最小生成树。

• 举个例子： 对于图1中的连通带权图，按Kruskal算法选取边的过程如图3。
  

[注]：无向连通带权图 --> 邻接矩阵

• 用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵；

• 每条带权无向边（v，w）的权存入矩阵c[v][w]；矩阵其余项为∞。

• 以图1为例：
  $$邻接矩阵A=\left[\begin{array}{cccccc}\infty & 6& 1& 5& \infty & \infty \\ 6& \infty & 5& \infty & 3& \infty \\ 1& 5& \infty & 5& 6& 4\\ 5& \infty & 5& \infty & \infty & 2\\ \infty & 3& 6& \infty & \infty & 6\\ \infty & \infty & 4& 2& 6& \infty \end{array}\right]$$

二、算法实现

1. Prim算法

// 【贪心算法】最小生成树问题 - Prim算法
#include <iostream> 
using namespace std;

#define M 9999	// maxint，inf，大数
const int N = 6;// 无向连通带权图的 顶点数

void Prim(int n, int c[][N + 1]);

int main()
{
	// 无向连通带权图的邻接矩阵，行和列下标从1开始
	int c[N + 1][N + 1] = {
		{M,	M,	M,	M,	M,	M,	M},
		{M,	M,	6,	1,	5,	M,	M},
		{M,	6,	M,	5,	M,	3,	M},
		{M,	1,	5,	M,	5,	6,	4},
		{M,	5,	M,	5,	M,	M,	2},
		{M,	M,	3,	6,	M,	M,	6},
		{M,	M,	M,	4,	2,	6,	M},
	};
	
	cout << "无向连通带权图的矩阵为：\n";
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
			cout << c[i][j] << "\t";
		cout << endl;
	}

	cout << "\nPrim算法最小生成树选边次序：" << endl;
	Prim(N, c);
	
	return 0;
}

void Prim(int n, int c[][N + 1])
{
	// 顶点j属于V-S，closest[j]是顶点j在S中的 最邻接顶点
	int closest[N + 1];	// j的 最邻接顶点
	// 顶点j属于V-S，顶点j到closest[j]和S中的其它邻接顶点k相比
	// c[j][closest[j]] <= c[j][k]，即最小权值
	int lowcost[N + 1];	// 最小权值，c[j][closest[j]]

	bool s[N + 1];		// 顶点集合S

	s[1] = true;		// 初始S={1}

	//初始化
	for (int i = 2; i <= n; i++)
	{
		closest[i] = 1;
		lowcost[i] = c[1][i];
		s[i] = false;
	}

	for (int i = 1; i < n; i++)
	{
		int min = M;
		int j = 1;
		// 找出V-S中使权值最小的顶点j
		for (int k = 2; k <= n; k++)
		{
			if ((lowcost[k] < min) && (!s[k]))
			{
				min = lowcost[k];
				j = k;
			}
		}
		// 找到符合贪心选择方式的边，将顶点j加入到集合S
		cout << closest[j] << "--" << j << endl;
		s[j] = true;

		// 找到一条边后，更新数组closest和lowcost
		for (int k = 2; k <= n; k++)
		{
			if ((c[j][k] < lowcost[k] && (!s[k])))
			{
				lowcost[k] = c[j][k];
				closest[k] = j;
			}
		}
	}
}

2. Kruskal算法（这是书上的，待续…）

// 【贪心算法】最小生成树问题 - Kruskal算法

template <class Type>
class EdgeNode
{
	friend ostream& operator <<(ostream&, EdgeNode<Type>);
	friend bool Kruskal(int, int, EdgeNode<Type>*, EdgeNode<Type>*);
	friend int main(void);

public:
	operator Type() const
	{
		return weight;
	}
private:
	Type weight;
	int u, v;
};

template <class Type>
bool Kruskal(int n, int e, EdgeNode<Type> E[], EdgeNode<Type> t[])
{
	MinHeap<EdgeNode<Type>> H(1);
	H.Initialize(E, e, e);
	UnionFind U(n);

	int k = 0;
	while (e && k < n - 1)
	{
		EdgeNode<int> x;
		H.DeleteMin(x);
		e--;

		int a = U.Find(x.u);
		int b = U.Find(x.v);

		if (a != b)
		{
			t[k++] = x;
			U.Union(a, b);
		}
	}
	H.Deactivate();
	return (k == n - 1);
}

3. 运行结果展示

三、友情链接~

• 其它一些常见算法请参阅此链接~

---

最后，非常欢迎大家来讨论指正哦！