棱镜算法(Prim算法)的概要http://www.Sina.com)，用图论中的算法可以在加权连通图中检索http://www.Sina.com。 也就是说普里姆算法（Prim算法）(英语： vertex ) graphtheory ) ) )，其所有边的权重之和也是最小的。 该算法于1930年由捷克数学家ggdgtx (英文： Vojtch Jarnk )发现； 1957年被美国计算机科学家怡园的帽子(Robert C. Prim )独立发现。1959年，紧张的香菇再次发现了该算法。 因此，在某些情况下，prime算法也被称为DJP算法、al智能树叶算法或prime智能树叶算法。
算法说明输入：设顶点集合为v，边集合为e的加权连通图； 初始化： V n e w V_{new} Vnew ={x}其中x是集合v中的任意节点(起点)，E n e w E_{new} Enew ={}，为空； 重复以下操作，直到V n e w V_{new} Vnew=V。
a .在集合e中选择权重最小的边u，v。 其中，u是集合V n e w V_{new} Vnew中的要素，v不在V n e w V_{new} Vnew的集合中，且vV (满足上述条件，即存在多个具有相同权重的边时，选择任意一个
将b.v放入集合V n e w V_{new} Vnew，将u，v边放入集合E n e w E_{new} Enew； 输出：使用集合V n e
w V_{new} Vnew和 E n e w E_{new} Enew来描述所得到的最小生成树。 图示 简略证明反证法：假设prim生成的不是最小生成树
设prim生成的树为G0假设存在 G m i n G_{min} Gmin使得cost( G m i n G_{min} Gmin)< cost( G 0 G_{0} G0) 则在 G m i n G_{min} Gmin中存在< u,v>不属于 G 0 G_{0} G0将< u,v>加入 G 0 G_{0} G0中可得一个环，且< u,v>不是该环的最长边(这是因为< u,v>∈ G m i n G_{min} Gmin)这与prim每次生成最短边矛盾故假设不成立，命题得证 基本操作函数prim(n)：建立最小生成树，并输出其权值和
代码模板(含详细注释)这里用 http://poj.org/problem?id=1258 作为模板题
#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 110 //最多顶点数#define MAX 0x3f3f3f3f //模拟无穷大int map[N][N]; //存储各顶点间的权值int flag[N]; //标记是否已纳入树int dis[N]; //已纳入点和其余各点的最小权值int prim(int n) //qrdyd函数{ int i, j; int now; //记录新纳入的点 int min; //记录新纳入的点到其余已纳入的点的最小权值 int sum = 0; //最小生成树权值和 memset(dis, MAX, sizeof(dis)); //初始化dis数组为无穷大 memset(flag, 0, sizeof(flag)); //初始化flag数组，0表示此点未被纳入 /*这里随机选取了1号点为初始时被纳入的顶点*/ for(i = 1; i <= n; i++) dis[i] = map[1][i]; //与1号点与其他点的权值存入dis数组 dis[1] = 0; //一号点到其本身的权值为0 flag[1] = 1; //标记为已纳入 for(i = 1; i < n; i++){ //除去初始时随机纳入的点还有n-1个点应被纳入 now = min = MAX; //初始为无穷大表示两点间无通路 for(j = 1; j <= n; j++){ //遍历 if(flag[j] == 0){ if(dis[j] < min){ //寻找与已纳入各点权值最小的点 now = j; min = dis[j]; } } } if(now == MAX) //若now等于max，则证明所有与初始时纳入的点连通的点已全被纳入 break; sum += min; //将找到的点纳入并标记 flag[now] = 1; for(j = 1; j <= n; j++){ /* 遍历比较之前纳入点到未纳入点的权值的最小值 与刚纳入点到未纳入点的权值 并用dis[j]存储新的最小值 */ if(flag[j] == 0) if(dis[j] > map[now][j]) dis[j] = map[now][j]; } } if(i == n) //若i等于n则证明已经建立最小生成树 return sum; else return -1;}int main(void){ int i, j, k; int n; //顶点数 while(scanf("%d", &n) != EOF){ for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) scanf("%d", &map[i][j]); //输入i和j之间的距离 if((k = prim(n)) != -1) //调用prim函数 printf("%dn", k); else printf("烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫烫n"); } return 0;}模板题样例图解