prim.cpp

Prim 算法寻找最小生成树

/************************************************************************/
/*                       Prim 算法 寻找最小生成树						*/
/*						by gaobin 2005-11-13							*/
/************************************************************************/ 
#include "stdio.h"
#include "stdlib.h"

#define NODE_NUM	6		// 顶点个数
#define MPV  1024			// 最大权值

typedef int AdjType;
typedef struct {
	int start_vex;		// 始点
	int stop_vex;		// 终点
	AdjType weight;		// 权值
} Edge;		// 最小生成树的边类型

typedef int VexType;
typedef struct  {
	VexType vexs[NODE_NUM];
	AdjType adjs[NODE_NUM][NODE_NUM];
	int nNode;
} GraphMatrix;	// 图的邻接矩阵表示

void Prim(GraphMatrix *pgraph, Edge mst[]);
int FindMinEdge(Edge mst[], int si);
void Swap(Edge mst[], int mi, int si);
void Adjust(GraphMatrix *pgraph, Edge mst[], int si);

int main() {
	GraphMatrix graphmatrix =  {    {0},
									{ 0,	 10,   MPV,  MPV,   19,  21,
									  10,     0,    5,	 6,   MPV,  11,
									  MPV,     5,    0,   6,   MPV,  MPV,
									  MPV,	  6,    6,   0,   18,  14,
									  19,     MPV,  MPV,  18,    0,  33,
									  21,     11,  MPV,  14,   33,  0  },
									  NODE_NUM
								};
	int i;
	for ( i = 0; i < NODE_NUM; i++ ) {
		graphmatrix.vexs[i] = i;
	}
	Edge mst[NODE_NUM-1];
	Prim(&graphmatrix, mst);
	printf("startnode\tstopnode\t\tweight\n");
	for ( i = 0; i < NODE_NUM-1; i++ ) {
		printf("%d\t\t%d\t\t\t%d\n", mst[i].start_vex, mst[i].stop_vex, mst[i].weight);
	}
	return 0;
}


void Prim(GraphMatrix *pgraph, Edge mst[]) {
	int s0 = 0;
	//rand()%(NODE_NUM);
	int i;
	for ( i = 0; i < NODE_NUM-1; i++ ) {	// 初始化与V0相连的边集合
		mst[i].start_vex = s0;
		mst[i].stop_vex = i+1;
		mst[i].weight = pgraph->adjs[s0][i+1];
	}
	
	int si = 0, mi;	 // si 为U , V集合分界，指向V集合第一边
	for ( i = 0; i < NODE_NUM-1; i++ ) {
		mi = FindMinEdge(mst, si);		// 在剩余V集合中寻找最小边
		Swap(mst, mi, si);				// 将最小边与V中第一边交换
		si++;				// 将该最小边加入U集合中
		Adjust(pgraph, mst, si);		// 调整V集合中的边
	}
}


int FindMinEdge(Edge mst[], int si) {
	int i, res = MPV;
	int ri = si;
	for ( i = si; i < NODE_NUM-1; i++ ) {
		if ( mst[i].weight >= 0 && mst[i].weight < res ) {
			res = mst[i].weight;
			ri = i;
		}
	}	
	return ri;
}


void Swap(Edge mst[], int mi, int si) {
	Edge tmp;
	tmp = mst[mi];
	mst[mi] = mst[si];
	mst[si] = tmp;
}


void Adjust(GraphMatrix *pgraph, Edge mst[], int si) {
	int i, ni = mst[si-1].stop_vex, j;
	for ( i = si; i < NODE_NUM-1; i++ ) {
		j = mst[i].stop_vex;
		if ( pgraph->adjs[ni][j] >= 0 
			 && pgraph->adjs[ni][j] < mst[i].weight )	
			 // 以新加入边终点为始点的边权值小于当前权值，更新mst中V集合中的边
		{
			mst[i].weight = pgraph->adjs[ni][j];
			mst[i].start_vex = ni;
			mst[i].stop_vex = j;
		}
	}
}