text1.cpp

最小生成树的kruskal算法之二.rar

// 最小生成树kruskal算法2

#include <stdio.h>
#include <stdlib.h>
#define MaxVex 10	//最大顶点数
#define MaxEdge 20	//最大边数

// 用邻接矩阵表示
typedef struct 
{
	int begin;
	int end;
	int weight;
} edge;

typedef struct
{
	int adj;
	int weight;
} AdjMatrix[MaxVex][MaxVex];

typedef struct
{
	AdjMatrix arc;
	int vexnum,edgenum;
} MGraph;

void CreatGraph(MGraph *);	//创建图
void sort(edge *,MGraph *);	//排序
void Swapn(edge *,int,int);	//交换两条边
void Kruskal(MGraph *);		//构造最小生成树
int  Find(int *,int);		//找连通分支的尾部

void main()
{
	MGraph *G=(MGraph*)malloc(sizeof(MGraph));
	if(G==NULL) exit(1);
	CreatGraph(G);
	Kruskal(G);
}

// 通过输入n条边数据创建图
void CreatGraph(MGraph *G)
{
	int i,j,n,m,w;
	printf("请输入顶点数和边数: ");
	scanf("%d,%d",&G->vexnum,&G->edgenum);

	//初始化图
	for(i=1; i<=G->vexnum; i++)
		for(j=1; j<=G->vexnum; j++)
			G->arc[i][j].adj=G->arc[j][i].adj=0;

	printf("\n依次输入%d条边的两个顶点和权值：\n\tV1,V2,W\n",G->edgenum);
	for(i=1; i<=G->edgenum; i++) 
	{
		printf("第%d条边: ",i);
		scanf("%d,%d,%d",&n,&m,&w);
		G->arc[n][m].adj=G->arc[m][n].adj=1;
		G->arc[n][m].weight=w;
	}

	printf("\n邻接矩阵为:\n");
	for(i=1; i<=G->vexnum; i++)
	{ 
		for(j=1; j<=G->vexnum; j++)
			printf("%d ",G->arc[i][j].adj);
		printf("\n");
	}
}

// 对权值进行排序
void sort(edge edges[],MGraph *G) 
{
	int i,j;
	for(i=1; i<G->edgenum; i++)
		for(j=i+1; j<=G->edgenum; j++)
			if(edges[i].weight>edges[j].weight) Swapn(edges,i,j);
	printf("\n权值排序后:\n");
	for(i=1; i<=G->edgenum; i++)
		printf("<%d, %d>  %d\n",edges[i].begin,edges[i].end,edges[i].weight);
}

// 交换Edge i和j的相关信息
void Swapn(edge *edges,int i,int j) 
{
	int temp;   
	temp=edges[i].begin;  
	edges[i].begin=edges[j].begin;
	edges[j].begin=temp;
	temp=edges[i].end;  
	edges[i].end=edges[j].end;
	edges[j].end=temp;
	temp=edges[i].weight;  
	edges[i].weight=edges[j].weight;
	edges[j].weight=temp;
}

// 构造最小生成树
void Kruskal(MGraph *G) 
{
	int i,j,n,m,k=1;
	int link[MaxEdge];	//连通分支
	edge edges[MaxEdge];	//边集

	//收集边信息
	for(i=1; i<G->vexnum; i++)
	{
		for(j=i+1; j<=G->vexnum; j++)
		{
			if(G->arc[i][j].adj==1)
			{
				edges[k].begin=i;
				edges[k].end=j;
				edges[k].weight=G->arc[i][j].weight;
				k++;
			}
		}
	}

	sort(edges,G);	//排序
	for(i=1; i<=G->edgenum; i++) link[i]=0;

	printf("\n最小生成树为:\n");
	for(i=1; i<=G->edgenum; i++)
	{
		n=Find(link,edges[i].begin);
		m=Find(link,edges[i].end);
		if (n != m)
		{
			link[n]=m;
			printf("<%d, %d>  %d\n",edges[i].begin,edges[i].end,edges[i].weight);
		}
	}
	printf("\n");
}

// 找连通分支的尾部
int Find(int *link,int f) 
{
	while(link[f]>0) f=link[f];
	return f;
}