无以言表我对着代码懵了两个小时终于看懂了的鸡冻，手写程序大法好哇，【或者只是我太久没敲代码了。。】个人感觉这个算法还是有点粗鲁，大量的遍历，比较中意最小生成树的另一个算法，一会搞懂它的代码再说。
最小生成树： 图G是树当且仅当以下任意条件成立：1》G有|V|-1条边，无环；【v为图中节点数目】
2》G有|V|-1条边，连通；
3》任意两点之间只有唯一的简单路径；
4》Gl连通，但删除任意一条边之后就不连通。
最小生成树：在一个带权的【带权的：连接各点的边上有值，通常表示距离，花费等等】无相连通图中，各边权和【即各边价值的和】最小的一颗生成树即为原图的最小生成树。
prime算法求最小生成树：【如果不了解，图，生成树这类的概念的不建议直接看算法，虽然看明白之后就是一个二阶矩阵，呃，，反正我是把之前的补了之后才看明白的。】
算法思想：prim算法是一种贪心算法，其从原图A【"A"代表一个图！】任意挑选一个点point，【想想为啥么任意，最小生成树无论挑选哪条边，所有的节点必须与原图相同，一个不能落下；再联系树的连通性：从任意一点出发，可到达任意一点；是第一个都无所谓，生成好的最小树换一种提溜方式，所谓的起点也随之变化了】，将挑选的这一点point视为图B的起点【图B就是未来的天之骄子，最小生成树】。
然后在原图A中找，找与起点point相连的各个边，每一条边，瞅瞅谁最小，把这条最小的边以及这个边对应着的点p2，一并加入到图B中。现在有了小小收获，看看B中此时有什么，起点point与一条它能连到的最小的一条边，以及该边的另一端p2，通通收入囊中了。
我们的目标是将所有的点都搞到B中去，好歹现在多了一个帮手，再找谁？从p2开始找吗？还是挑选起点point的次小边？看看我们算法的本质，贪心！当然两者都要，【这里算法实现略微变态，有点难懂，记住这里的思想过程】，我们要将魔爪伸向剩余的点了，我们一开始比较的时候将起点point能连接的边都拽了出来，每一个边背后都带着一个无辜点，当然也有点不与起点point相连逃过一劫，但是现在起点point多了一个帮手p2，不与起点相连但与p2相连的点自然也被拽了出来，这时候的问题是，与起点和p2都相连的点，到底留下哪一条边呢？当然凭实力说话，谁的权值更小留哪一条边。
先在将所有被起点与p2点一起拽出来的边再进行比较，留下最小的那一条边以及该边拽出来的那个点，然后就是这三个点一起作威作福，拽剩下的几个点了，处理过程同上，，直到所有的点都从A中被拽过来。
【说的有点复杂，一如我死活看不懂代码最后一步一步写时内心的疯狂diss】，简单来说，就是不断从图A中挑选与图B中点相连的最短的边以及对应点加入图B，直至所有点加入图B。
算法步骤：选用图中的任意一个顶点V0,从V0开始生成最小生成树：
1》初始化dist[v0]=0,其他点的距离值dist[i]=正无穷；其中dist [ i ] 表示集合VB中的点到VA中的点的距离值，
2》经过N次如下步骤操作，最后得到一个含N个顶点，N-1条边的最小生成树:
1>选择一个未标记的点K，并且dist [ k ] 的值是最小的；
2>标记点K进入集合VA;
3>以K为中间点，修改未标记点 j ,即VB中的点到VA的距离值；
3》得到最有生成树T。
代码实现： //最小生成树//prim算法#include<iostream>#include<cstring>#define INF 10000using namespace std;const int N = 6;bool visit[N];int dist[N] = { 0, };int G[N][N] = { {INF,7,4,INF,INF,INF}, //INF代表两点之间不可达 {7,INF,6,2,INF,4}, {4,6,INF,INF,9,8}, {INF,2,INF,INF,INF,7}, {INF,INF,9,INF,INF,1}, {INF,4,8,7,1,INF} };int prim(int cur)//首个挑选到的节点 cur{ int index = cur; int sum = 0; //最短路径之和 int i = 0 , j = 0; cout << index << " "; memset(visit,false, sizeof(visit)); //标记数组，初始化，全部未访问 visit[cur] = true; for(i = 0; i < N; i++)//与第一个挑走的点i，相连的所有边的距离，存入dist[]中 dist[i] = G[cur][i];//初始化，每个与a邻接的点的距离存入dist for(i = 1; i < N; i++)//遍历表中每一个节点 { int minn= INF; //与另一个表相连的最小边，初始化，为一个极大值 for(j = 0; j < N; j++) { if(!visit[j] && dist[j] < minn) //找到未访问的点中，距离当前最小生成树距离最小的点 { minn = dist[j]; //不断更新与点cur的相连点的最短距离 index = j; } } visit[index] = true;//标记距离最短的刚刚被拿走的那个节点，已经被访问过 cout << index << " "; sum += minn; for(j = 0; j < N; j++) //已经进入最小树的点的可及范围，与刚进入最小树的点相比较，比之前点可到达某点的距离较小，更新当前最小生成树的可及范围的最小值***** { if(!visit[j] && dist[j]>G[index][j]) //执行更新，如果点距离当前点的距离更近，就更新dist { dist[j] = G[index][j]; } } } cout << endl; return sum; //返回最小生成树的总路径值}int main(){ cout << prim(0) << endl;//从顶点a开始 return 0;}代码自己扣吧，难点在与dist[ ]的更新操作上，如果看不明白，，，看注释。