最小生成树_kruscal.cxx

最小生成树

#include <iostream>
#include <algorithm>
using namespace std;
//===============================//
//并查集用于集合判断，rank保证集合树的平衡
int set[1024];                         
int rank[1024];
void makeset(int i)          //并查集初始化；
{
	set[i] = i;
}
int findset(int a)            //查找节点a的父节点，如果父节点为根节点则返回根节点，否则继续向上查找
{
	if(set[a] != a)
		return findset(set[a]);
	else return set[a];
}
void link(int a, int b)         //连接两个元素a，b所在集合；
{
	if(rank[a] > rank[b])       //a节点树高，则将b所在树接到a树根下；
		set[b] = a;
	else if(rank[a] < rank[b])  //反之同理
		set[a] = b;
	else                        //两树高相同则任意选取一树连到另一树下；并更新rank[]；
	{
		rank[a]++;
		set[b] = a;
	}
}
//=================================//
//边结构体 lid, rid，distance ,分别保存边的左顶点右顶点和边长；
struct MSTree
{
	int distance, lid, rid;
	bool operator<(const MSTree &a)const          //<运算符重载并用sort函数根据边长对结构体排序；
	{
		if(distance < a.distance)return true;
		else return false;
	}
};
int findstr(char *stra, int n);                //查找边的编号
MSTree s[1024];                                //结构体数组
char str[1024][64];                            //顶点信息
char str1[64], str2[64];
int main()
{
	int n, i, m, dis, left, right, sum;
	printf("please input the vetrix ans the edge number\n");      //输入
	while(scanf("%d %d", &n, &m) == 2)                     //n为顶点个数，m为边个数
	{
		printf("please input the name of vetrix\n");
		for(i = 0; i < n; i++)
			scanf("%s", str[i]);                          //读入顶点信息
		printf("please input the edge\n");                
		for(i = 0; i < m; i++)                            //读入边信息
		{
			scanf("%s %s %d", str1, str2, &dis);
			s[i].distance = dis;
			s[i].lid = findstr(str1, n);                 //查找边并对边结构lid，rid赋值
			s[i].rid = findstr(str2, n);
		}
		sort(s, s+m);                                    //调用stl-algorithm库函数排序
		for(i = 0; i < n; i++)
			makeset(i);                                  //并查集初始化
		
		for(i = 0, sum = 0; i < n-1; i++)
		{
			left = findset(s[i].lid);                       //查找左顶点所在集合
			right = findset(s[i].rid);                      //查找右顶点所在集合  
			if(left != right)                               //如果两个顶点所在集合不同则将两个集合合并
			{
				printf("%d :%s %s %d\n", i, str[s[i].lid], str[s[i].rid], s[i].distance);//打印mst边；
				link(left, right);                          //两个集合合并
				sum += s[i].distance;                       //sum保存mst总消费
			}
		}
		printf("the minimum cost is %d\n", sum);            //打印mst总消费
		printf("please input the vetrix ans the edge number\n");	
	}
}
int findstr(char *stra, int n)                            //查找顶点，返回顶点编号；
{
	for(int i = 0; i < n; i++)
		if(strcmp(stra, str[i]) == 0)return i;           //stra和str[i]相同返回i标号
	return -1;
}