最小生成树

克鲁斯卡尔算法

介绍

克鲁斯卡尔（Kruskal 算法）是一种常见并且好写的最小生成树算法，该算法的基本思想是从小到大加入边，是个贪心算法。
tip. 无向连通图的最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

图示

先将原图中所有边去除，算法的每一轮在保证不出现环的情况下添加一条权最小的边。

算法的关键在于判断图是否出现环，可以用并查集进行实现。

算法示例

struct edge
{
	int u, v;
	int weight;
};
vector<int> father; //记录每个节点的父亲
vector<vector<int>> result; //存储最后获得的各条边

bool compare(edge a, edge b)
{
	return a.weight < b.weight;
}

int findfather(int a)
{
	while (a != father[a])
	{
		a = father[a];
	}
	return a;
}
void kruskal(int n, vector<edge> Edge)
{
	father.resize(n);
	sort(Edge.begin(), Edge.end(), compare);
	for (int i = 0; i < n; ++i)
	{
		father[i] = i;
	}
	for (int i = 0; i < Edge.size() && result.size() < n-1; ++i)
	{
		int u = Edge[i].u;
		int v = Edge[i].v;
		if (findfather(u) != findfather(v)) //判断父节点是否相同
		{
			result.push_back(vector<int>{u,v});
			father[findfather(u)] = father[findfather(v)]; //将两点并入一个集合中
		}
	}
	if (result.size() != n - 1)
	{
		cout <<  result.size()  << "该图不连通" << endl;
		return;
	}
	else
	{
		cout << "最小生成树的各边如下：" << endl;
		for (int i = 0; i < result.size(); ++i)
		{
			cout << result[i][0] << "->" << result[i][1] << endl;
		}
	}
}

---

算法分析

1. 时间复杂度 $O(m\log m)$
2. 空间复杂度 $O(n^2)$

普里姆算法

介绍

普里姆算法（Prim 算法）不同于克鲁斯卡尔算法的加边，而是需要加点。

图示

从任意点开始，首先加入与该点距离最近的点，构成一个两点图。再加入一个与两点中任意一点距离最近的点，构成一个三点图，以此类推，直到所有点连通。（图中不能形成环）

算法示例

class Prim{
	private:
		std::vector<int>father;
		std::vector<std::vector<int>>result;
		std::vector<std::vector<int>>graph;
		int n;
		int findfather(int a)
		{
			while (a != father[a])
			{
				a = father[a];
			}
			return a;
		}
	public:
		Prim(int n, std::vector<std::vector<int>>graph):n(n),graph(graph){
			father.resize(n);
			for(int i=0;i<n;++i){
				father[i] = i;
			}
		}
	public:
		std::vector<std::vector<int>> getTree(){
			std::unordered_set<int>isVisit;
			isVisit.emplace(0);
			while(isVisit.size()<n){
				std::vector<int>minNode={INT_MAX/2, -1, -1};// 加入点到图距离，加入点的序号，加入边对应的另一点
				for(auto it = isVisit.begin(); it != isVisit.end(); ++it){
					int currentNode = *it;
					for(int i=0;i<n;++i){
						if(minNode[0]>graph[currentNode][i]&&!isVisit.count(i)){
							if (findfather(currentNode) != findfather(i)) //判断父节点是否相同
							{
								minNode = {graph[currentNode][i], i, currentNode};
							}
						}
					}
				}
        if(minNode[1]==-1){
          std::cout << "该图不连通" << std::endl;
          return result;
        }
				isVisit.emplace(minNode[1]);
				// 加入集合
				father[findfather(minNode[1])] = father[findfather(minNode[2])];
				result.emplace_back(std::vector<int>{minNode[1], minNode[2]});
			}
			return result;
		}
};

输出的result即为最小生成树的每一边

---

算法分析

1. 时间复杂度 $O(n^2+m)$
2. 空间复杂度 $O(n^2)$