《大话数据结构》最小生成树——Prim算法

/*
  2014-6-24
  思想：将点集合分为两部分，U代表已经确定的节点集合，V表示还未确定的点集合
  从U中找到节点i,从V中找到节点j，使得(i-j)边的距离为min(U-V)——类似于贪心算法。
	
  难点：确定一个节点将从V阵营叛变到U时，应该更新V阵营中节点与新集合U'(包含了叛变节点k后)的距离。
  
  理解：策反一个敌人时，则敌对阵营中和该敌人关系紧密的节点与我方的关系也“可能”改善。

*/
#include <iostream>
#include <queue>   
using namespace std;


typedef char VertexType; /* 顶点类型应由用户定义 */
typedef int EdgeType; /* 边上的权值类型应由用户定义 */

#define MAXSIZE 9 /* 存储空间初始分配量 */
#define MAXEDGE 15
#define MAXVEX 9
#define INFINITY 65535

typedef struct
{
	VertexType vexs[MAXVEX]; /* 顶点表 */
	EdgeType arc[MAXVEX][MAXVEX];/* 邻接矩阵，可看作边表 */
	int numVertexes, numEdges; /* 图中当前的顶点数和边数 */ 
}MGraph;


/* ****************************************************** */


void CreateMGraph(MGraph *G)
{
	int i, j;

	G->numEdges=15;
	G->numVertexes=9;

	/* 读入顶点信息，建立顶点表 */
	G->vexs[0]='A';
	G->vexs[1]='B';
	G->vexs[2]='C';
	G->vexs[3]='D';
	G->vexs[4]='E';
	G->vexs[5]='F';
	G->vexs[6]='G';
	G->vexs[7]='H';
	G->vexs[8]='I';


	for (i = 0; i < G->numVertexes; i++)/* 初始化图 */
	{
		for ( j = 0; j < G->numVertexes; j++)
		{
			G->arc[i][j]=INFINITY;
		}
	}

	G->arc[0][1]=10;
	G->arc[0][5]=11;

	G->arc[1][2]=18; 
	G->arc[1][8]=12; 
	G->arc[1][6]=16;
	
	G->arc[2][3]=22; 
	G->arc[2][8]=8; 

	G->arc[3][4]=20;
	G->arc[3][7]=16;
	G->arc[3][6]=24;
	G->arc[3][8]=21;

	G->arc[4][5]=26;
	G->arc[4][7]=7;

	G->arc[5][6]=17; 
	G->arc[6][7]=19; 

	
	for(i = 0; i < G->numVertexes; i++)
	{
		for(j = i+1; j < G->numVertexes; j++)
		{
			G->arc[j][i] =G->arc[i][j];
		}
	}

}
 
int visited[MAXVEX]; /* 访问标志的数组 */

void Prim(MGraph G)
{
	int min,i,j,k;
	int adjvex[MAXVEX];
	int lowcost[MAXVEX];
	
	lowcost[0]=0;	/*值为0表示此下表的定点已经加入生成树*/
	adjvex[0]=0;	/*初始化第一个定点下表为0*/
	
	for(i=1;i<G.numVertexes;++i)	
	{
		lowcost[i]=G.arc[0][i];		/* 将v0顶点与之有边的权值存入数组*/
		adjvex[i]=0;	/* 初始化为V0的下表 */
	}

	for(i=1;i<G.numVertexes;++i){
		min=INFINITY;
		
		j=1;	k=0;
		while(j<G.numVertexes){
			if(lowcost[j]!=0 && lowcost[j]<min){
				min=lowcost[j];
				k=j;
			}
			++j;
		}
		
		printf("(%d,%d)",adjvex[k],k);
		lowcost[k]=0;

		for(j=1;j<G.numVertexes;++j){	/*  节点k成功加入生成树了，需要更新其余节点到节点集合u的距离，是更新*/
			if( lowcost[j]!=0 && G.arc[k][j]<lowcost[j] )
			{
				lowcost[j]=G.arc[k][j];
				adjvex[j]=k;
			}
		}

	}


}


int main(void)
{    
	MGraph G;
	CreateMGraph(&G);
	
	Prim(G);

	cout<<endl;
	return 0;
}