tu.h

一个用vc实现的Kruskal算法

#include<iostream.h>

#define maxsize 10

struct enode{
	int v1,v2;
	int weight;
};

class kruskal{                                    
public:
	kruskal(int gragh[][maxsize],int v,int e);    
	~kruskal();
	void esort(int low,int high);
	bool isconnect(int v1,int v2);
	void insert_e(int v1,int v2,int weight);
	void least_tree();
	void print();
private:
	enode *ep;
	int (*vp)[maxsize];
	bool (*connect)[maxsize];
	int v_num,e_num;
};

kruskal::kruskal(int gragh[][maxsize],int v,int e)
{
	v_num=v;
	e_num=e;
	vp=new int[v_num][maxsize];
	connect=new bool[v_num][maxsize];
	for(int i=0;i<v_num;i++)
		for(int j=0;j<v_num;j++){
			vp[i][j]=0;
			connect[i][j]=false;
		}
	ep=new enode[e_num+1];
	int k=0;
	for(i=0;i<v_num;i++)
		for(int j=i;j<v_num;j++)
			if(gragh[i][j]!=0){
				ep[k].weight=gragh[i][j];
				ep[k].v1=i+1;
				ep[k].v2=j+1;
				k++;
			}
}

kruskal::~kruskal()
{
	delete []ep;
	delete []vp;
	delete []connect;
}

void kruskal::esort(int low,int high)
{
	int l=low,h=high;
	if(low<high){
		enode temp;
		temp.weight=ep[low].weight;
		temp.v1=ep[low].v1;
		temp.v2=ep[low].v2;
		while(low<high){
			while(low<high&&ep[high].weight>=temp.weight)
				high--;
			ep[low].weight=ep[high].weight;
			ep[low].v1=ep[high].v1;
			ep[low].v2=ep[high].v2;
			while(low<high&&ep[low].weight<=temp.weight)
				low++;
			ep[high].weight=ep[low].weight;
			ep[high].v1=ep[low].v1;
			ep[high].v2=ep[low].v2;
		}
		ep[low].weight=temp.weight;
		ep[low].v1=temp.v1;
		ep[low].v2=temp.v2;
		int partition=low;
		esort(l,partition-1);
		esort(partition+1,h);
	}
}

void kruskal::insert_e(int v1,int v2,int weight)
{
	vp[v1-1][v2-1]=weight;
	vp[v2-1][v1-1]=weight;
	connect[v1-1][v2-1]=true;
	connect[v2-1][v1-1]=true;
}

bool kruskal::isconnect(int v1,int v2)
{
	for(int m=0;m<v_num;m++)
		for(int i=0;i<v_num;i++)
			for(int j=0;j<v_num;j++)
				connect[i][j]=(connect[i][m]&&connect[m][j])||connect[i][j];//||vp[i][j];
	return connect[v1-1][v2-1];
}

void kruskal::least_tree()
{
	for(int i=0;i<e_num;i++){
		int v1=ep[i].v1;
		int v2=ep[i].v2;
		if(!isconnect(v1,v2))
			insert_e(v1,v2,ep[i].weight);
	}
}

void kruskal::print()
{
	for(int i=0;i<v_num;i++)
		for(int j=i;j<v_num;j++)
			if(vp[i][j]!=0)
				cout<<i+1<<'-'<<j+1<<'\t';
	cout<<endl;
}