minispantree.cpp

我自己编写的一个C++ kruskal最小生成树程序

#include<iostream>
#include<fstream>
using namespace std;

struct edge
{
	int u;
	int v;
	float w;
};

void kruskal(struct edge *E,int n)
{
	int i,j,m1,m2,sn1,sn2,k;
	int * vest=new int [n];
	for(i=0;i<n;i++)
		vest[i]=i;
	k=1;
	j=0;
	while(k<n)
	{
		m1=E[j].u;
		m2=E[j].v;
		sn1=vest[m1];
		sn2=vest[m2];
		if(sn1!=sn2)
		{
			cout<<"边 ("<<m1<<","<<m2<<") 权值 :"<<E[j].w<<endl;
			k++;
			for(i=0;i<n;i++)
				if(vest[i]==sn2)
					vest[i]=sn1;
		}
		j++;
	}
	delete []vest;
}

void readfile(float **data,int n)
{
	fstream fin;
	fin.open("data.txt");
	int i,j;
	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			fin>>data[i][j];
}

int transform(float **data,struct edge E[],int n)
{
	int i,j,k=0;
	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
		{
			if(data[i][j]>0)
			{
				E=(struct edge*)realloc(E,sizeof(struct edge)*(k+1));
				E[k].u=i;
				E[k].v=j;
				E[k].w=data[i][j];
				k++;
			}
		}
		return k;
}

void sort(edge *E,int n)
{
	int i,j;
	edge temp;
	//cout<<n;
	for(i=0;i<n-1;i++)
		for(j=0;j<n-i+1;j++)
		{
			if(E[j].w>E[j+1].w)
			{
				temp=E[j];
				E[j]=E[j+1];
				E[j+1]=temp;
			}
		}
}


void printdata(float **data,int n)
{
	int i,j;
	for(i=0;i<n;i++)
	{
		for(j=0;j<n;j++)
		{
			cout.width(2);
			if(data[i][j]==0)
				cout<<"∞"<<' ';
			else cout<<data[i][j]<<' ';
		}
		cout<<endl;
	}
}


int main()
{
	int n,i,c;
	cout<<"请输入顶点个数：";
	cin>>n;
	float **data=new float*[n];
	for(i=0;i<n;i++)
		data[i]=new float[n];
	cout<<endl<<"从文件读入邻接矩阵……"<<endl<<endl;
	readfile(data,n);
	cout<<"邻接矩阵为："<<endl<<endl;
	printdata(data,n);
	edge * E=new edge;
	c=transform(data,E,n);
	sort(E,c);
	cout<<endl<<"最小生成树路径为："<<endl<<endl;
	kruskal(E,n);
	cout<<endl;
	return 0;
}