mgraph.h

最少生成树问题

#include "stdio.h"
#include "stdlib.h"

#define MAXE 200

typedef char ELEM;

typedef struct edge	
{  
	ELEM bv,tv;
	int w;
}EdgeNode,EdgeSet[MAXE];	//边集类型，存储一边条的起始顶点为bv,终止顶点为tv和权w 

void CreateEdgeSet(EdgeSet &edgeset,int arcnum)
{
	EdgeNode edgenode,t;
	printf("请输入每条边依附的节点和权值：\n");
	for( int i=1; i<=arcnum; i++ )
	{
		scanf( "%c,%c,%d", &edgenode.bv, &edgenode.tv, &edgenode.w );
		getchar();	//接收回车符
		edgeset[i]=edgenode;
	}
	for( i=1; i<arcnum; i++)
		for( int j=1; j<=arcnum-1; j++)
			if( edgeset[j].w > edgeset[j+1].w )
			{
				t=edgeset[j];
				edgeset[j]=edgeset[j+1];
				edgeset[j+1]=t;
			}	//对边以权值从小到大的顺序排序
}


ELEM seeks(int set[],ELEM v)
{  
	ELEM i=v;
    while(set[i]>0)i=set[i];	
    return(i);	//被边连到一起的节点返回相同的值
} 

void MiniSpanTree_Cruscal(EdgeSet edgeset, int vexnum, int arcnum)		//edgeset为权按从小到大排序的边集数组
{   
	int set[MAXE];	//顶点的标志数组
	int i=1;		//i表示获取的生成树中的边数，初值为1
	int j=1;		//j表示edgeset中的下标，初始值为1
	ELEM v1, v2;
    for( int n=1; n<=vexnum; n++ ) set[n]=0;		//给set中每个元素赋初值
    while( j<vexnum && i<=arcnum )		//检查该边是否加入到生成树中       
    {   
		v1=seeks(set,edgeset[i].bv); 
		v2=seeks(set,edgeset[i].tv);
        if( v1!=v2 )	//当 v1,v2不在同一集合，该边加入生成树
        { 
			printf("%c,%c\n",edgeset[i].bv,edgeset[i].tv);
            set[v1]=v2;	//连到一起的节点加入到同一集合
            j++;
         }
         i++;
     }//while
}