文章作者：ktyanny 文章来源： 转载请注明，谢谢合作。
ktyanny最近很心烦，因为前天兴致勃勃想写个prim算法，结果很郁闷，看了两下也没想到怎么实现，囧了半天放弃了…… 但是还是不死心呐，一大早起来，不对劲，怎么舍友全走了，原来我已经睡过了两节课了，要不是肚子饿了的话我可能还会继续睡下去的。那就待会去上三四节的os课吧，先打开电脑去农场看菜回来，哇咔咔，好多菜可以摘啊，看来起床时是摘菜的最佳时间呐。
从农场拿了个大丰收回来，又想起心里那个结还没了断，又拿起算法导论左看右看的，还是没感觉，汗……突然想起严蔚敏阿姨那本数据结构，诶，写得倒是蛮详细的，仔细数了一下，嘿嘿，13行代码，小case，嘎嘎……二话不说看完，恍然大悟中，上os课的时候，就拿起算法导论的那个图左画右画的，就是下面这个图：（在这里强调一下，如果你不知道最小生成树的概念，可以点击查看最小生成树得到概念和性质）
上面的这个图是个很好的例子，其实不用不明白，这个图的最小生成树是不唯一的，认真思考就知道为什么了。
留念一下os课上的我的鬼画虎的作品哈哈……（没带相机，吃完饭回到宿舍拍的）
好了，流水账就记录那么多了。
普里姆算法的基本思想：
从连通网络 N = { V, E }中的某一顶点 u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。
Prim算法的形式描述如下：
置T为任意一个顶点； 求初始候选边集； while （T中结点数＜n） ｛ 从候选边集中选取最短边（u，v）； 将（u，v）及顶点v，扩充到T中； 调整候选边集； ｝
为了更方便了解，贴上几个刚刚拍下来的prim算法过程的图片吧
好吧，就这样吧。
下面是写得很辛苦的代码：
/* by ktyanny2009.12.15 */ #include < stdio.h > #include < stdlib.h > #include < iostream > using namespace std; const int MAXN = 0x7fffffff ; const int MAX = 105 ; /* 顶点上限 */ typedef int vrtype;vrtype g[MAX][MAX]; /* 图的带权邻接矩阵 */ vrtype prim(vrtype g[][MAX], int n){ int i, j, k, minn, closest[MAX], ans = 0 ; vrtype lowcost[MAX]; for (i = 2 ; i <= n; i ++ ) { lowcost[i] = g[ 1 ][i]; closest[i] = 1 ; } closest[ 1 ] = 0 ; /* 第一个节点是在U集合里的 */ for (i = 2 ; i <= n; i ++ ) { minn = MAXN; k = i; for (j = 1 ; j <= n; j ++ ) { if (lowcost[j] < minn && closest[j] != 0 ) { minn = lowcost[j]; k = j; } } /* 打印边 printf("(%c, %c)", closest[k], k); */ ans += minn; closest[k] = 0 ; /* k并入U集合 */ for (j = 2 ; j <= n; j ++ ) { if (closest[j] && g[k][j] < lowcost[j]) { lowcost[j] = g[k][j]; /* 更新最小权值 */ closest[j] = k; /* 记录新的起点 */ } } } return ans;}