《大话数据结构》最小生成树——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;
}