最小生成树之Prime法

关于最小生成树的概念，在前一篇文章中已经讲到，就不在赘述了。下面介绍Prime算法：

其基本思想为：从一个顶点出发，选择由该顶点出发的最小权值边，并将该边的另一个顶点包含进来，然后找出由这两个顶点出发的最小边，依此类推，直至包含所有的顶点。如果期间构成环，就舍弃该边，继续寻找最小边。下面以具体实例来说明算法的过程：

具体的程序实现如下：

#include<stdio.h>

#define N 6 //顶点数

#define MAX 10000

typedef struct

{

	int startvex,endvex;//边的起点和终点2

	int length;//边的权值

}edge;

int flag[N]={0};//标志顶点是否被选定

int flag1=0;//记录边的终点

int flag2=0;//记录边的起点

void Prime(int  i,int dist[N][N],edge T[N-1])

{

	int j,k,min;

	int num=0;

	flag[i]=1;//包含顶点置为1

	while(num<5)//6个顶点则有5条边

	{

		min=MAX;

		for(j=0;j<N;j++)//从已选边中找到最小权值的边

		{

			if(flag[j]==1)

				for(k=0;k<N;k++)

				{

					if(dist[j][k]<min)

					{

						min=dist[j][k];

						flag1=k;//记录当前最小权值边的起点和终点

						flag2=j;

					}

				}

		}

		if(flag[flag1]!=1)//判断是否构成回路

		{

			T[num].startvex=flag2;//将找到的最小权值边记录

			T[num].endvex=flag1;

			T[num].length=dist[flag2][flag1];

			num++;

			flag[flag1]=1;

		}

		dist[flag2][flag1]=MAX;//将已经选择的边的权值置为无穷大

	}

	for(int i=0;i<N-1;i++)

		printf("start=%d,end=%d,length=%d\n",T[i].startvex,T[i].endvex,T[i].length);

}

void main()

{

	int dist[N][N]={{MAX,10,MAX,MAX,19,21},

					{10,MAX,5,6,MAX,11},

					{MAX,5,MAX,6,MAX,MAX},

					{MAX,6,6,MAX,18,14},

					{19,MAX,MAX,18,MAX,33},

					{21,11,MAX,14,33,MAX}};

	edge T[N-1];

	Prime(1,dist,T);//1代表从序号为一的顶点开始

}

运行结果如下：

注意最小生成树不是唯一的，但是总权值是一样的。

注：如果程序出错，可能是使用的开发平台版本不同，请点击如下链接：解释说明

巴特西

最小生成树之Prime法

最新文章

热门文章