最小生成树kruska（邻接表）.cpp

最小生成树kruska（邻接表）

#include<iostream.h>
#include<limits.h>
#include <algorithm> 
using namespace std; 

#define NumEd 50
const int NumVer = 50;
const int maxlength = 100;
typedef struct node{
	int adjvex;
	int cost;  
	struct node *next;
}edgenode;
typedef struct{
     char vertex;
     edgenode *firstedge;
}vertexnode;
typedef struct{
	vertexnode vexlist[NumVer];
    int n,e;
}adjgraph;
typedef struct{
	int father;
	int count;/* 加权*/
}nodes;
void Kruskal( int* s ,adjgraph *g);
void creatmgraph(adjgraph *g);
void UNION(int A,int B,nodes *C);
int FIND(int x, nodes* C);
void INITIAL(int A ,nodes *C);
void EQUIVA(nodes *S);
int s[NumEd],s1[NumEd][3];
void creatgraph(adjgraph &g);
void main()
{
   adjgraph g;
    creatgraph(g);
    Kruskal(s ,&g);
}
void creatgraph(adjgraph &g)
{
	int tail,head,cost;
	cout<<"请输入顶点个数和边数\n";
	cin>>g.n>>g.e;
	for(int i=0;i<g.n;i++){
 //       cout<<"请输入顶点"<<i<<"值\n";
//		cin>>g.vexlist[i].vertex;
		g.vexlist[i].firstedge=NULL;
	}
	for(i=0;i<g.e;i++){
        cout<<"请输入头结点和邻接点域（下标）以及权值\n";
		cin>>tail>>head>>cost;
		edgenode*p=new edgenode;
        p->adjvex=head;
		p->next = g.vexlist[tail].firstedge;
		p->cost=cost;
        g.vexlist[tail].firstedge= p;
		p = new edgenode;
		p->adjvex= tail; 
		p->next = g.vexlist[head].firstedge;//链入第head 号链表的前端
	    p->cost=cost;
		g.vexlist[head].firstedge= p;
        s[i]=cost;
        s1[i][0]=tail;
		s1[i][1]=head;
		s1[i][2]=0;
	}
}
void Kruskal( int* s , adjgraph*g)
{  
	int i=0,j,k,n=0,n1,n2;
    edgenode *p;
	nodes*MFSET;
    MFSET=new nodes[(g->n)+1];
    for(i=1; i<(g->n+1);i++)
        INITIAL(i,MFSET);/*使集合S只包含元素i */
  int ncomp=g->n ;/*结点个数*/
   sort( s,s+g->e) ;
   cout<<"最小生成树的边是：\n";
   i=0;
while ( ncomp> 1&&i<g->n) 
{
/*    for(j=0;j<g->n&&n==0;j++)
	{
      for(k=0;k<g->n&&n==0;k++)
	  {
            if(s[i]==(g->edge[j][k]))
			{
				n=1;
				g->edge[j][k]=0;
			}
	  }
	}*/
    for(k=0;k<g->n&&n==0;k++)
	{
		p=g->vexlist[s1[k][0]].firstedge;
		while((p->adjvex)!=s1[k][1])
		{
			p=p->next;
		}
		if(s[i]==(p->cost)&&s1[k][2]==0)
		{
			s1[k][2]=1;
			j=s1[k][0];
			k=s1[k][1]-1;
			n=1;
		}
	}
    n1=FIND(j+1,MFSET);
    n2=FIND(k+1,MFSET);
    if (n1!=n2)
	{
       UNION(n1,n2,MFSET);
       cout<<'('<<j<<','<<k<<')';
       ncomp--;
	   
	}
	n=0;
	i++;
}
}
void UNION(int A,int B,nodes *C)
{ 
	if(C[A].count>C[B].count)
	{
		/* |B|<|A| */
		C[B].father=A; /* 并入A */
		C[A].count+=C[B].count;
	}
	else
	{
		/*|A|<|B|*/
		C[A].father=B; /* 并入B */
		C[B].count+=C[A].count;
	}
}
int FIND(int x, nodes* C)
{
	int tmp=x;
    while(C[tmp].father!=0)/*>0,未到根*/
       tmp=C[tmp].father; /* 上溯*/
    return tmp;
}
void INITIAL(int A ,nodes *C)
{ 
	C[A].father=0;
    C[A].count=1;
}