main.cpp

Prim算法的实现

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

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

int Now;//已经放入结点数
int Use[1001];//是否被使用
int Node[10001];
vector<E> All;//初始边
vector<E> Save;//支撑树中的边
int n;//结点数
int total;//边数


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

void Perform()
{
	for(int i=0;i<total;i++)
	{
		if(Use[i]==0)
		{
			if(Node[All[i].a]==1&&Node[All[i].b]==0)
			{
				Node[All[i].b]=1;
				Use[i]=1;
				Now++;
				Save.push_back(All[i]);

				return;
			}//加入离Save中已出现结点相连接的边中权最小的边
			else if(Node[All[i].b]==1&&Node[All[i].a]==0)
			{
				Node[All[i].a]=1;
				Use[i]=1;
				Now++;
				Save.push_back(All[i]);

				return;
			}
		}
			
	}
}

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);
		total++;
		
	}//输入


	sort(All.begin(),All.end(),Small);//比较大小

	/*for(vector<E>::iterator i=All.begin();i!=All.end();i++)
		cout<<(*i).d<<endl;*/

	for(int i=0;i<=n-1;i++)
		Node[i]=0;
	for(int i=0;i<=total-1;i++)
		Use[i]=0;//初始化
	Now=0;

	Save.push_back(All[0]);//放入第一个结点(此处放入的是权最小的边)

	Node[All[0].a]=1;
	Node[All[0].b]=1;
	Use[0]=1;
	Now+=2;

	while(Now<=n-1)//Now=n-1则构成最短支撑树
	{
		Perform();
	}
	
	for(vector<E>::iterator s=Save.begin();s!=Save.end();s++)
		cout<<'v'<<(*s).a<<(*s).b<<"  ";
	cout<<endl;//输出

	return 0;
}