prims.cpp

Prims算法的程序

#include "stdio.h"
#include "malloc.h"
#define  INT_MAX 100
#define  MAX_NUM  6

typedef struct ArcCell{
	int adj;
}ArcCell ,AdjMatrix[MAX_NUM+1][MAX_NUM+1];

typedef struct {
	char vex[MAX_NUM];
    AdjMatrix  arcs;
	int vexnum;
}MGraph;

// 用PRIM算法从第u个顶点出发构造网G的最小生成树T.
// 记录从顶点集U到V-U的代价的最小的边的辅助数组定义为：
typedef struct close{
 	char adjvex;		// U中的顶点
 	int	 lowcost;
}close,closedge1[ MAX_NUM ];


int LocateVex(MGraph G,char u);

void MiniSpanTree_PRIM( MGraph G, char u);
int  minimum(closedge1  closedge);
void main()
{
  MGraph G;
  //close  closedge[ MAX_NUM ];
  
  
  G.vexnum=6;
  G.vex[0]='a';G.vex[1]='b';G.vex[2]='c';
  G.vex[3]='d';G.vex[4]='e';G.vex[5]='f';
  for(int i=0;i<G.vexnum;i++)
	  for(int j=0;j<G.vexnum;j++)
		  G.arcs[i][j].adj=INT_MAX ;
	  
  /*G.arcs[1][2].adj=6;   G.arcs[1][3].adj=1;   G.arcs[1][4].adj=5;

  G.arcs[2][1].adj=6;   G.arcs[2][3].adj=5;   G.arcs[2][5].adj=3;
  
  G.arcs[3][1].adj=1;    G.arcs[3][2].adj=5; G.arcs[3][4].adj=5;
  G.arcs[3][5].adj=6; G.arcs[3][6].adj=4;
  
  G.arcs[4][1].adj=5; G.arcs[4][3].adj=5; G.arcs[4][6].adj=2;
  
  G.arcs[5][2].adj=3; G.arcs[5][3].adj=6; G.arcs[5][6].adj=6;
  
  G.arcs[6][3].adj=4; G.arcs[6][4].adj=2; G.arcs[6][5].adj=6;*/

 /* G.arcs[1][2].adj=1;   G.arcs[1][3].adj=2;   G.arcs[1][4].adj=3;

  G.arcs[2][1].adj=1;   G.arcs[2][3].adj=4;   G.arcs[2][5].adj=6;
  
  G.arcs[3][1].adj=2;    G.arcs[3][2].adj=4; G.arcs[3][4].adj=5;
  G.arcs[3][5].adj=7; G.arcs[3][6].adj=8;
  
  G.arcs[4][1].adj=3; G.arcs[4][3].adj=5; G.arcs[4][6].adj=9;
  
  G.arcs[5][2].adj=6; G.arcs[5][3].adj=7; G.arcs[5][6].adj=10;
  
  G.arcs[6][3].adj=8; G.arcs[6][4].adj=9; G.arcs[6][5].adj=10;*/
 // for(int m=1;m<=G.vexnum;m++) 
//		 G.arcs[m][m].adj=0;
  //k=LocateVex(G,'a');
  //printf("%d",k);
  G.arcs[1][2].adj=6;   G.arcs[1][3].adj=1;   G.arcs[1][4].adj=5;
  G.arcs[1][5].adj=6;   G.arcs[1][6].adj=5;  
  MiniSpanTree_PRIM(  G, 'a');
  
}
int LocateVex(MGraph G,char u)
{
  for(int i=0;i<G.vexnum;i++) 
     if(u==G.vex[i])
		 return i;
  return -1;
}
int  minimum(closedge1  closedge)
{
   int m= INT_MAX;
   int k1=0;
   for (int i=0;i<MAX_NUM;i++)
	   if((closedge[i].lowcost<=m)&&(closedge[i].lowcost>0))
	   {  
		  m=closedge[i].lowcost;
          k1=i;  
	   }
    return k1;
}
void MiniSpanTree_PRIM( MGraph G, char u)
{
	int k;
	closedge1 closedge;
	
    k = LocateVex( G, u );	// 顶点U的位置
	// 辅助数组初始化
	for(int j = 0; j < G.vexnum; j++ )
	{
		if( j != k )
		{
			closedge[j].adjvex =  u;
			closedge[j].lowcost=  G.arcs[k][j].adj;
			
		}
	}
	closedge[k].lowcost = 0;	// 初始U = {u}
	//closedge[k].adjvex='q';

	for(int i = 1; i < G.vexnum; i++ )
	{
	    // 求T的下一个结点k，k满足的关系为: 
		// 所有在V-U的顶点集合中，代价非0的代价最小的顶点的位置。
		k=minimum(closedge);
		// 输出
		printf("  %c,%c  ", closedge[k].adjvex, G.vex[k] );
			
		// 第k个顶点并入U
		closedge[k].lowcost = 0;
		// 更新V-U中的顶点的closedge，
		// 主要看新这些顶点和新加入的顶点k的比较
		for( j = 0; j < G.vexnum; j++ )
		{
			if( G.arcs[k+1][j+1].adj < closedge[j].lowcost )
			{
				closedge[j].adjvex = G.vex[k];
			    closedge[j].lowcost= G.arcs[k+1][j+1].adj;			
			}
		}
	}
}