MST最小生成树及Prim普鲁姆算法

MST在前面学习了Kruskal算法，还有一种算法叫做Prim的。这两者的区别是Prim算法适合稠密图，比如说鸟巢这种几乎所有点都有相连的图。其时间复杂度为O(n^2)，其时间复杂度与边的数目无关；而kruskal算法的时间复杂度为O(eloge)，跟边的数目有关，适合稀疏图。

prim算法

基本思想：假设G＝(V，E)是连通的，TE是G上最小生成树中边的集合。算法从U＝{u0}（u0∈V），TE＝{ 空集 }开始。重复执行下列操作：

1.在所有u∈U，v∈V-U的边(u，v)∈E中找一条权值最小的边(u0,v0)并入集合TE中，同时v0并入U，直到V＝U为止；接下里以 v0为边的起点，继续寻找权值最小的边并入集合TE中，依次往复；

2.最后，TE中必有n-1条边，T=(V，TE)为G的最小生成树。

Prim算法的核心：始终保持TE中的边集构成一棵生成树，也就是它与Kruskal算法的主要区别是，Prim是一直保持一种串联的状态而不遵从整体的贪心算法。其实初始点uo的选择可以随意，一般做题题目条件会给出或者取最小的权值边。

其实现的代码如下：

#include <stdio.h>

#include <string.h>

#include <stdlib.h>

#define infinity 1000000

#define max_vertexes 6

typedef int Graph[max_vertexes][max_vertexes];

void prim(Graph G,int vcount,int father[])

{

int i,j,k;

int lowcost[max_vertexes];

int closeset[max_vertexes],used[max_vertexes];

int min;

for (i=0;i<vcount;i++)

  {

/* 最短距离初始化为其他节点到1号节点的距离 */

    lowcost[i]=G[0][i];

    /* 标记所有节点的依附点皆为默认的1号节点 */

     closeset[i]=0;

  used[i]=0;

    father[i]=-1;

}

used[0]=1; /*第一个节点是在s集合里的*/

/* vcount个节点至少需要vcount-1条边构成最小生成树 */

  for (i=1;i<=vcount-1;i++)

   {

 j=0;

     min = infinity;

       /* 找满足条件的最小权值边的节点k */

     for (k=1;k<vcount;k++)

         /* 边权值较小且不在生成树中 */

 if ((!used[k])&&(lowcost[k]<min))

    {

              min =  lowcost[k];

              j=k;

            }

    father[j]=closeset[j];

printf("%d %d\n",j+1,closeset[j]+1);//打印边

used[j]=1;;//把第j个顶点并入了U中

for (k=1;k<vcount;k++)

         /* 发现更小的权值 */

   if (!used[k]&&(G[j][k]<lowcost[k]))

{

                  lowcost[k]=G[j][k];/*更新最小权值*/

      closeset[k]=j;;/*记录新的依附点*/

    }

   }

}

int main()

{

FILE *fr;

int i,j,weight;

Graph G;

int fatheer[max_vertexes];

for(i=0; i<max_vertexes; i++)

for(j=0; j<max_vertexes; j++)

G[i][j] = infinity;

fr = fopen("prim.txt","r");

if(!fr)

{

printf("fopen failed\n");

exit(1);

}

while(fscanf(fr,"%d%d%d", &i, &j, &weight) != EOF)

{

G[i-1][j-1] = weight;

G[j-1][i-1] = weight;

}

prim(G,max_vertexes,fatheer);

return 0;

}

邻接矩阵的形式进行存储的实现：

#include <stdio.h>

#define n 6

#define MaxNum 10000  /*定义一个最大整数*/

/*定义邻接矩阵类型*/

typedef int adjmatrix[n+1][n+1];   /*0号单元没用*/

typedef struct{

	int fromvex,tovex;

	int weight;

}Edge;

typedef Edge *EdgeNode;

int arcnum;     /*边的个数*/

/*建立图的邻接矩阵*/

void CreatMatrix(adjmatrix GA){

	int i,j,k,e;

	printf("图中有%d个顶点\n",n);

	for(i=1;i<=n;i++){

		for(j=1;j<=n;j++){

			if(i==j){

				GA[i][j]=0;         /*对角线的值置为0*/

			}

			else{

				GA[i][j]=MaxNum;    /*其它位置的值置初始化为一个最大整数*/

			}

		}

	}

	printf("请输入边的个数：");

	scanf("%d",&arcnum);

	printf("请输入边的信息，按照起点，终点，权值的形式输入：\n");

	for(k=1;k<=arcnum;k++){

		scanf("%d,%d,%d",&i,&j,&e);  /*读入边的信息*/

		GA[i][j]=e;

		GA[j][i]=e;

	}

}

/*初始化图的边集数组*/

void InitEdge(EdgeNode GE,int m){

	int i;

	for(i=1;i<=m;i++){

		GE[i].weight=0;

	}

}

/*根据图的邻接矩阵生成图的边集数组*/

void GetEdgeSet(adjmatrix GA,EdgeNode GE){

	int i,j,k=1;

	for(i=1;i<=n;i++){

		for(j=i+1;j<=n;j++){

			if(GA[i][j]!=0&&GA[i][j]!=MaxNum){

				GE[k].fromvex=i;

				GE[k].tovex=j;

				GE[k].weight=GA[i][j];

				k++;

			}

		}

	}

}

/*按升序排列图的边集数组*/

void SortEdge(EdgeNode GE,int m){

	int i,j,k;

	Edge temp;

	for(i=1;i<m;i++){

		k=i;

		for(j=i+1;j<=m;j++){

			if(GE[k].weight>GE[j].weight){

				k=j;

			}

		}

		if(k!=i){

			temp=GE[i];GE[i]=GE[k];GE[k]=temp;

		}

	}

}

/*利用普里姆算法从初始点v出发求邻接矩阵表示的图的最小生成树*/

void Prim(adjmatrix GA,EdgeNode T){

	int i,j,k,min,u,m,w;

	Edge temp;

	/*给T赋初值，对应为v1依次到其余各顶点的边*/

	k=1;

	for(i=1;i<=n;i++){

		if(i!=1){

			T[k].fromvex=1;

			T[k].tovex=i;

			T[k].weight=GA[1][i];

			k++;

		}

	}

	/*进行n-1次循环，每次求出最小生成树中的第k条边*/

	for(k=1;k<n;k++){

		min=MaxNum;

		m=k;

		for(j=k;j<n;j++){

			if(T[j].weight<min){

				min=T[j].weight;m=j;

			}

		}

		/*把最短边对调到k-1下标位置*/

		temp=T[k];

		T[k]=T[m];

		T[m]=temp;

		/*把新加入最小生成树T中的顶点序号赋给j*/

		j=T[k].tovex;

		/*修改有关边，使T中到T外的每一个顶点保持一条到目前为止最短的边*/

		for(i=k+1;i<n;i++){

			u=T[i].tovex;

			w=GA[j][u];

			if(w<T[i].weight){

				T[i].weight=w;T[i].fromvex=j;

			}

		}

	}

}

/*输出边集数组的每条边*/

void OutEdge(EdgeNode GE,int e){

	int i;

	printf("按照起点，终点，权值的形式输出的最小生成树为：\n");

	for(i=1;i<=e;i++){

		printf("%d,%d,%d\n",GE[i].fromvex,GE[i].tovex,GE[i].weight);

	}

}

void main(){

	adjmatrix GA;

	Edge GE[n*(n-1)/2],T[n];

	CreatMatrix(GA);

	InitEdge(GE,arcnum);

	GetEdgeSet(GA,GE);

	SortEdge(GE,arcnum);

	Prim(GA,T);

	printf("\n");

	OutEdge(T,n-1);

}

巴特西

MST最小生成树及Prim普鲁姆算法

最新文章

热门文章