c7_kruskal.cpp

这个是严蔚敏版的数据结构上机教程中的部分源代码

/*
Kruskal
BY:wangyucao
*/ 
  

#include<stdio.h>
#include<stdlib.h>
#define M 20//边数
#define MAX 20//顶点数

typedef struct 
{
 int begin;
 int end;
 int weight;
}edge;

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

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

void CreatGraph(MGraph *);
void sort(edge* ,MGraph *);
void MiniSpanTree(MGraph *);
int  Find(int *, int );
void Swapn(edge *, int, int);


void CreatGraph(MGraph *G)//构图
{
	int i, j,n,m;

	printf("请输入顶点数和边数:");
	scanf("%d%d",&G->vexnum,&G->arcnum);
 
    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;
 


	for ( i = 1; i <= G->arcnum; i++)//输入边和权值 
	{
		//printf("\n请输入边的2个顶点");
		scanf("%d%d",&n,&m);
		while(n < 0 || n > G->vexnum || m < 0 || m > G->vexnum)
		{
			printf("输入的数字不符合要求 请重新输入:");
			scanf("%d%d",&n,&m);
		}
     
		G->arc[n][m].adj = G->arc[m][n].adj = 1;
		getchar();
		//printf("\n请输入%d与%d之间的权值:", n, m);
		scanf("%d",&G->arc[n][m].weight);
		G->arc[m][n].weight=G->arc[n][m].weight;
	}
    /*
	printf("邻接矩阵为:\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->arcnum; i++)
		 for ( j = i + 1; j <= G->arcnum; j++)//上三角
			if (edges[i].weight > edges[j].weight)
				Swapn(edges, i, j);

/*	printf("权排序之后的为:\n");
	for (i = 1; i <= G->arcnum; i++)
		printf("< %d, %d >   %d\n", edges[i].begin, edges[i].end, edges[i].weight);*/
}   




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 MST(MGraph *G)//生成最小生成树 
{
	int i, j, n, m,k = 1,parent[M];

	edge edges[M];
 
	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++;
			 }//get edges[k]

        
    sort(edges, G);
    for (i = 1; i <= G->arcnum; i++)
		parent[i] = 0;
  

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




int Find(int *parent, int f)//判断是不是环 
{
	while ( parent[f] > 0)
	{
		f = parent[f];
	}
    return f;
}

int main()//主函数 
{
	 MGraph *G;

	 G = (MGraph*)malloc(sizeof(MGraph));
	 if (G == NULL) {
		printf("memory allcation failed,goodbye");
		exit(1);
	 }
    
	CreatGraph(G);
    MST(G);//MiniSpanTree(G);
    system("PAUSE");
	return 0;
}