/************************************************************************/
/* 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;
}
}
}
