最小生成树kruskal.cpp

贪心算法解一系列算法经典问题

// 最小生成树kruskal算法

#include <stdio.h>
#include <stdlib.h>
#define Vn 6	//顶点数

// 边集结构
typedef struct 
{
	int begin;
	int end;
	int weight;
} edge;

// 邻接矩阵
int Graph[Vn][Vn]=
{
	{0},  //1
	{6},  //2
	{1, 5},  //3
	{5, 0, 5},  //4
	{0, 3, 6},  //5
	{0, 0, 4, 2, 6}  //6
};

void Edges(edge a[],int &n);  //收集边信息
void Sort(edge a[],int);  //排序(可更换其它排序算法)
void Kruskal(edge E[],int);  //构造最小生成树
int Find(int link[],int);  //找连通分支的尾部

void main()
{
	int En=0;  //边数
	edge Es[Vn*(Vn-1)/2];  //边集
	Edges(Es,En);
	Sort(Es,En);
	Kruskal(Es,En);
}

//收集边信息
void Edges(edge a[],int &n)
{
	printf("邻接矩阵：\n");
	for(int i=0; i<Vn; i++)
	{
		for(int j=0; j<=i; j++)
		{
			printf("%d\t",Graph[i][j]);
			if(Graph[i][j]>0)
			{
				a[n].begin=j+1;
				a[n].end=i+1;
				a[n++].weight=Graph[i][j];
			}
		}
		printf("\n");
	}
}

// 对边的权值进行排序
void Sort(edge a[],int n) 
{
	for(int i=0; i<n; i++)
		for(int j=i+1; j<n; j++)
			if(a[i].weight>a[j].weight)
			{
				int temp=a[i].begin;
				a[i].begin=a[j].begin;
				a[j].begin=temp;
				temp=a[i].end;
				a[i].end=a[j].end;
				a[j].end=temp;
				temp=a[i].weight;
				a[i].weight=a[j].weight;
				a[j].weight=temp;
			}
	printf("\n权值排序后:\n");
	for(i=0; i<n; i++)
		printf("<%d, %d>  %d\n",a[i].begin,a[i].end,a[i].weight);
}

// 构造最小生成树
void Kruskal(edge E[],int N)
{
	int n,m,link[Vn]={0};
	printf("\n最小生成树:\n");
	for(int i=0; i<N; i++)
	{
		n=Find(link,E[i].begin);
		m=Find(link,E[i].end);
		if (n != m)
		{
			link[n-1]=m;
			printf("<%d, %d>  %d\n",E[i].begin,E[i].end,E[i].weight);
		}
	}
	printf("\n");
}

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