fff.txt

用Kruskal算法求最小生成树

#include <iostream>
#include <iomanip>
using namespace std;
#define MAXNODE 100
#define MAXEDE  100

 struct  edge
{ 
	int   v1,v2;
	int   cost;
};

class MGraph
{
private:
	int n,e;     //定义无向图的顶点数和边数
	int vexs[MAXNODE],i;  //定义顶点信息
	edge key[MAXEDE];
    
	
public: 
	MGraph(){
		cout<<"Please input the numbers of dingdianshu  and bianshu(like this dingdianshu,dianshu): ";//请输入顶点数和边数（输入格式为：顶点数，边数）
		cin>>n>>e;      //输入顶点数和边数
		//cout<<"Please input the information of dingdian :";//请输入顶点信息（输入格式为：i）
		//for(i=0;i<n;i++)
		//	cin>>vexs[i];    //输入顶点信息，建立顶点表
    }
	
    void CreateMGraph()
	{
		// 建立无向图G的邻接矩阵存储
	    //	MGraph();
		int i,j,k;
		int bian[100][100];
		int cst;
		for(i=0;i<n;i++)
			for(j=0;j<n;j++)
				bian[i][j]=0;  //初始化邻接矩阵
		cout<<"Please input the two dingdian and their cost(like this i,j,cst):";//请输人每条边对应的两个顶点及其权值（输入格式为:i,j,q）
		for(k=1;k<=e;k++)
		{
			cout<<"Please input the dingdian i and j and its cost:";
			cin>>i>>j>>cst;     //输入e条边信息，建立邻接矩阵
			bian[i][j]=cst;
			bian[j][i]=cst;
			key[k].cost=cst;     //建立一个关键码数组 ，方便后面的堆排序
			key[k].v1=i;     //第k条边的第一个顶点为i
			key[k].v2=j;     //第k条边的第二个顶点为j 
		}
	} //CreateMGraph
	
	void HeapAdjust(int s,int t)
	{
		//edges[s...t]中的记录关键码除eedges[s]外均满足堆的特性，本算法将其进行筛选，使其成为大顶堆
		int  i,j;
		edge  rc;
		rc=key[s];
		i=s;
		for(j=2*i;j<=t;j=2*j)  //沿关键码较小的孩子结点向下筛选
		{ 
			if(j<t && key[j].cost<key[j+1].cost)
				j=j+1;  //j指向edges的关键码较小的孩子
			if(rc.cost>key[j].cost)
				break;   //不用调到叶子就到位了
			key[i]=key[j];
			i=j;  //准备继续向下调整 
		} 
        
		key[i]=rc;   //插入 
	}   
	
	void Heapsort()
	{
		//大顶堆排序 
		int i;
		edge tmp;
		for(i=e/2;i>0;i--)      //将edges[1]....edges[n]建成堆 
			HeapAdjust(i,e);
		for(i=e;i>1;i--)
		{
			tmp=key[1];        //堆顶edges[1]与堆底edges[i]交换 
			key[1]=key[i];
			key[i]=tmp;
            HeapAdjust(1,i-1);   //将edges[1]...edges[i-1]重新调整为堆 
		}
	}
		
		
		int Find(int father[MAXEDE], int v)
		{
			//寻找定点v所在树的根结点
			int t;
			t=v;
			while(father[t]>=0)
				t=father[t];
			return(t); 
		} 

		void Kruskal()
		{
			//用Kruskal方法构造有n个顶点图edges的最小生成树
			//edges[]中的数据已按cost值由小到大排序
			int  father[MAXEDE];
			//对于n个顶点的网，设置1个数组father[n]，
			//其初值为father[i]=-1(i=0,1...n-1),表示各个顶点在不同的连通分量上，然后依次取出edges数组中的每条边的 2 个顶点，查处他们所属的连通分量 ，若
			//不属于同一个连通分量，则将这条边作为最小生成树的边输出，并合并他们所属的连通分量， 
			int i,j,vf1,vf2;
			for(i=0;i<n;i++)
				father[i]=-1;
			i=1;
			j=1;
			while(i<MAXEDE && j<n)
			{ 
				vf1=Find(father,key[i].v1);
				vf2=Find(father,key[i].v2);
				if(vf1!=vf2)
				{
					father[vf2]=vf1;
					j++;
					cout<<key[i].v1<<key[i].v2<<endl;
				}
				i++;
			}  
		}
	};//MGraph
	
	
	
	int  main()
	{  
		//1。然后按边上的权值进行堆排序 ，传入的是边信息 
		//2。然后将排好序的边传到 Kruskal中，进行最小生成树的构造 
		MGraph g;
		g.CreateMGraph();
		g.Heapsort();
		g.Kruskal();
		return 1;
	}