图的最小生成树—Kruskal算法

图的最小生成树—Kruskal算法

Kruskal算法的思想是：

1. 选择最短的边
2. 将边的起点和终点加入集合中，将边标记后选出
3. 再次选择最短的边，且该边的起点和终点不在同一集合中（避免产生回路）
4. 再次将点纳入集合，将边选出
5. 重复步骤3，4，直到将n-1条边选出到生成树（最小生成树只有n-1条边）中。

Kruskal算法是对边进行遍历，只要每次选出来的边是合法的且最短的，生成树就是最小生成树

• 合法的：边的起点终点不在同一集合中，即不产生回路
• 最短的：满足前提条件下权值最小的

如何判断两点是否在同一集合中？：利用并查集

示例题目：

镖局运镖需要向路上的绿林好汉打点，每条路的打点费用有高有低，镖局如何选择道路，使得镖局可以到达任意城镇且打点费用最少？

数据给出格式如下：

6 9
2 4 11
3 5 13
4 6 3
5 6 4
2 3 6
4 5 7
1 2 1
3 4 9
1 3 2

• 第一行两个数字 a b ，表示有a个城镇，b条道路
• 接下来b行，每行三个数字 u v w ，表示从 u城到v城的打点费用为w
• 输出选择过程和最终结果

解题代码

整体代码：

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;

multimap<int, pair<int, int>> roads;//存储图，利用了map的key值自动从小到大排序
int city, road;//城市和道路
int minleng = 0;//记录生成树的权值之和

//并查集函数
int findFather(int* cityArray, int v)
{
	if (cityArray[v] == v)
	{
		return v;
		//如果找到祖先，则返回
	}
	else
	{
		cityArray[v] = findFather(cityArray, cityArray[v]);
		return cityArray[v];
		//如果不是祖先，则一直查找祖先，这里使用了路径压缩
	}
}

//并查集合并函数
bool merge(int* cityArray,int v, int u)
{
	int t1 = findFather(cityArray,v);//找到v的祖先
	int t2 = findFather(cityArray,u);//找到u的祖先
	
	if (t1 != t2)//如果两个节点的祖先不相同，则两个节点没在同一集合中，要使用当前边，纳入集合
	{
		cityArray[t2] = t1;
		return false;
		//靠左原则
	}
	else//如果两个节点已经在同一集合中，则无需使用当前边
	{
		return true;
	}
}

int main()
{
	cin >> city >> road;
	int a, b, c;
	for (int i = 0; i < road; i++)
	{
		cin >> a >> b >> c;
		roads.insert(pair<int, pair<int, int>>(c, make_pair(a, b)));
	}//插入城市

	//初始化并查集数组
	int* cityArray = new int[city + 1];
	for (int i = 1; i <= city; i++)
	{
		cityArray[i] = i;
	}

	int cityA, cityB, leng,counter=0;
	for (multimap<int, pair<int, int>>::iterator it=roads.begin();it!=roads.end();it++)
	{
		cityA = it->second.first;//获取起点城市
		cityB = it->second.second;//获取终点城市
		leng = it->first;//获取该边的长度（权值）
		if (merge(cityArray, cityA, cityB) == false)//如果两个点没在同一集合中
		{
			cout << "第"<<counter+1<<"步选择了：" << cityA << " " << cityB << " " << leng << endl;
			minleng += leng;//将边加入最小生成树
			counter++;
		}
		if (counter == city - 1)//最小生成树只有n-1条边
		{
			break;
		}
	}

	cout << minleng;
	return 0;
}

1. 这里利用了map可以按key值从小到大排序，key值直接存储打点费用，value值则存储起点终点对组
2. 利用并查集判断两点是否在同一集合中
3. 利用迭代器对map进行遍历，注意取值的first，second要用指针（即->）

Kruskal算法代码：

int cityA, cityB, leng,counter=0;
for (multimap<int, pair<int, int>>::iterator it=roads.begin();it!=roads.end();it++)
{
	cityA = it->second.first;//获取起点城市
	cityB = it->second.second;//获取终点城市
	leng = it->first;//获取该边的长度（权值）
	if (merge(cityArray, cityA, cityB) == false)//如果两个点没在同一集合中，这里利用了并查集
	{
		cout << "第"<<counter+1<<"步选择了：" << cityA << " " << cityB << " " << leng << endl;
		minleng += leng;//将边加入最小生成树
		counter++;
	}
	if (counter == city - 1)//最小生成树只有n-1条边
	{
		break;
	}
}

• 对每一条边（已经排好序）进行遍历，选择合法的边

输出结果：

第1步选择了：1 2 1
第2步选择了：1 3 2
第3步选择了：4 6 3
第4步选择了：5 6 4
第5步选择了：3 4 9
19