爱站程序员基地图（来源：<<大话数据结构>>p250）
#include <stdio.h>#include <stdlib.h>#include <stdbool.h>/** 邻接矩阵, prim普里姆算法(属贪婪算法)，无向图，最小生成树* 代码实现<<大话数据结构>>p250 图7-6-6,v0至v8分别用ABCDEFGHI代替（不过打印过程还是用的下标）* 最终成生n-1条边的树，路径权值和最小*/#define MAX 9#define INFINITY 65535// 图结构体typedef struct {char vexs[MAX]; // 顶点的数组，顶点类型为了简单使用charint arc[MAX][MAX]; // 边表二维数组，值为权int numVex;}GRAPH, *PGRAPH;void create(PGRAPH);void gprint(GRAPH);void prim(GRAPH);void prim(GRAPH graph){int i, j, k, min;// 保存相关节点的数组（也可叫作父子(前后)关系，下标为当前节点，值为前一个节点，形成1条边）int adjVex[MAX];// 保存节点相关的边的最小权值(这个是随着程序不断迭代而更新的)int lowcost[MAX];// 循环处理前的初始化工作adjVex[0] = 0; // 以第1个顶点为开头，直接加入v0节点lowcost[0] = 0; // v0节点不需要再计算权值，标识为0，0还有个意思表示该节点已经加入最小生成树// 使用v0节点相关的数据，初始化上面2个数组for (i=0; i<graph.numVex; i++) {//先全部初始化为0，表示所有节点的前1个节点都先为v0adjVex[i] = 0;// v0节点相关的边权值加入数组，因为入口是v0节点，这些是目前可以看到的相关的边lowcost[i] = graph.arc[0][i];}/** 开始循环处理，次数为n-1，n为节点数*/// v0入口节点已经加入过数组不需要处理，所以从1开始for (i=1; i<graph.numVex; i++) {// 每轮都需要计算当前未加入最小生成树中的节点相关的最小权的边int min = INFINITY;// 先在lowcost数组中找出当前可以看到的边中，权值最小的那条边for (j=1; j<graph.numVex; j++) {if (lowcost[j] !=0 && lowcost[j] < min) {min = lowcost[j];k = j;}}// 新找到的最小权值的边的相关节点为新查找根节点，标识为0，放入最小生成树lowcost[k] = 0;printf(\"%d->%d\\n\", adjVex[k], k); //adjVex可以知道相关节点前后关系// 把符合条件的与新根节点(行)有关的边、节点信息更新到数组，供下一轮查找for (j=1; j<graph.numVex; j++) {if (lowcost[j] != 0 && graph.arc[k][j] < lowcost[j]) {lowcost[j] = graph.arc[k][j];adjVex[j] = k; // 只要找到的更新其前节点为k;}}}}void create(PGRAPH g){int i, j;g->numVex = 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->numVex; i++) {for (j=0; j<g->numVex; j++) {g->arc[i][j] = INFINITY;if (j == i)g->arc[i][j] = 0; //行列相等时表示自身，标识为0}}// 添加边及权值// A v0, B v1, C v2, D v3, E v4, F v5, G v6, H v7, I, v8g->arc[0][1] = 10;g->arc[1][0] = 10;g->arc[0][5] = 11;g->arc[5][0] = 11;g->arc[1][2] = 18;g->arc[2][1] = 18;g->arc[1][8] = 12;g->arc[8][1] = 12;g->arc[1][6] = 16;g->arc[6][1] = 16;g->arc[2][8] = 8;g->arc[8][2] = 8;g->arc[2][3] = 22;g->arc[3][2] = 22;g->arc[3][8] = 21;g->arc[8][3] = 21;g->arc[3][6] = 24;g->arc[6][3] = 24;g->arc[3][7] = 16;g->arc[7][3] = 16;g->arc[3][4] = 20;g->arc[4][3] = 20;g->arc[4][7] = 7;g->arc[7][4] = 7;g->arc[4][5] = 26;g->arc[5][4] = 26;g->arc[5][6] = 17;g->arc[6][5] = 17;g->arc[6][7] = 19;g->arc[7][6] = 19;}void gprint(GRAPH graph){int i, j;for (i=0; i<graph.numVex; i++) {for (j=0; j<graph.numVex; j++){printf(\"%6d \", graph.arc[i][j]);}putchar(\'\\n\');}}int main(void){GRAPH graph;create(&graph);gprint(graph);prim(graph);return 0;}
output
[root@8be225462e66 c]# gcc prim.c && ./a.out0 10 65535 65535 65535 11 65535 65535 6553510 0 18 65535 65535 65535 16 65535 1265535 18 0 22 65535 65535 65535 65535 865535 65535 22 0 20 65535 24 16 2165535 65535 65535 20 0 26 65535 7 6553511 65535 65535 65535 26 0 17 65535 6553565535 16 65535 24 65535 17 0 19 6553565535 65535 65535 16 7 65535 19 0 6553565535 12 8 21 65535 65535 65535 65535 00->10->51->88->21->66->77->47->3[root@8be225462e66 c]#
