main.cpp

Kruskal算法的实现

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

struct E
{
	int a,b;
	int d;
};

vector<E> All;//存储初始边
vector<E> Save;//存储结果
int n;//结点数
int Now=0;
int Use[1001];//判断Save中边是否已判断

bool Small(E a, E b)
{
	return a.d<=b.d;
}

bool Try(int p,int q)
{
	if(p==q)
	{
		return true;//已经找到回路
	}

	for(unsigned int i=0;i<Save.size();i++)
	{
		if(Save[i].a==p&&Use[i]==0)
		{
			Use[i]=1;
			if(Try(Save[i].b,q)==true)
			{
				return true;
			}
			Use[i]=0;//判断是否组成回路，继续深探
		}
		else if(Save[i].b==p&&Use[i]==0)
		{			
			Use[i]=1;
			if(Try(Save[i].a,q))
			{
				return true;
			}
			Use[i]=0;
		}
	}//继续寻找
	return false;
}

int main()
{
	E temp;

cout<<"请输入结点数"<<endl;

	cin>>n;
	
cout<<"请分别输入构成边的两根结点及边的权，如v23（10）则输入2 3 10 "<<endl;
cout<<"输入0则表示停止输入"<<endl;

	int Con;
	while(cin>>Con)
	{
		if(Con==0)
			break;
		else
		cin>>temp.b>>temp.d;
		temp.a=Con;
		All.push_back(temp);
		
	}//读入数据

	sort(All.begin(),All.end(),Small);//读入边并排序
	/*for(vector<E>::iterator i=All.begin();i!=All.end();i++)
		cout<<(*i).d<<endl;*/


	for(vector<E>::iterator t=All.begin();t!=All.end();t++)
	{

		if(Now>=n-1)
		{
			break;
		}//已经构成最短支撑树

		for(unsigned int i=0;i<Save.size();i++)
			Use[i]=0;

		if(Try((*t).a,(*t).b)==0)
		{
			Save.push_back(*t);
			Now++;
			/*cout<<"Now : "<<Now<<endl;*/
		}
	}


	for(vector<E>::iterator s=Save.begin();s!=Save.end();s++)
	cout<<'v'<<(*s).a<<(*s).b<<"  ";
	cout<<endl;//输出结果

	return 0;
}