也谈不上多懂，刚刚看了一下，自觉略懂略懂，因而记之，望有助于同志者。
先讲一讲最小生成树。。
现在我给你n个点，m条边(a,b,c a,b 为边的两端，c 为长度)，
请你得出最佳方案使这n个点连在一起的边的权值之和最小(总长度最小)。
PS：一条边两边都可以走，不是单方向的~~~ =。=
称之为无向图~~相对应的有有向图，就是一条边有方向限制~~~ =。=
最小生成树就是这么一个总长度最小的图(我也不知道为什么叫树)。。。。。
很容易可以看出只需要（n-1）条边吧。（为什么？）（不用多说）
也可以看出肯定没有环吧（不用多说）
OK最小生成树略微介绍一下。进入下一环节~~
★★★★★★★★★★★★★★★★★★★★★★★★★★★★
现在开始介绍prim算法：
我们把每一个点看做一个集合，，那么最终的结果就是所有集合 合到了一起。。
我们从点A开始考虑
一个点 A 和 能直接相连的点(就是有一条直接相接的路的，不用拐弯的)，
最少也有一条边相连（为什么？）（不用多说。。）
所以如果 A 与周围的点中 A->B 是最短的，那么 A,B 肯定是连通的。
为什么？我决定讲一下。。
{
我们把A点去掉，现在图中没有A点了，他的最小生成树中，每一个点都在树中，现在加入A点，为了使总权值最小，
那么连通A点的边要尽量小，所以………………(不用多说)
}
所以如果 A 与周围的点中 A->B 是最短的，那么 A,B 肯定是连通的。
于是乎，首先，把这条边扫进来。现在A,B连在一起了
但A,B不可能是孤立的啊，A,B肯定还和其他点连在一起（不用多说。。。。。）
我们简称（A,B）这个集合为S。。。所以S周围有很多边与S相连。。我们要总权值最小啊！！
所以选择其中与S相连的最短的边，拉进来！
现在S集合有三个点了。。S集合不是孤立的……在从周围贪心选择最短边，拉进来
当所有点都在这个集合中，，prim就执行完毕了。。
这样一个图，，我们随便选个点a1吧，，a1与周围的点中，距a2最近，只有1，所以把a2拉进来，，
貌似a4a5之间没有啊。。。。那就假定他无限大吧~~~=。=
现在a1 a2是一家了，距离a1a2最近的点有两个，a3，a4，这个就随便选一个呗，那就a3吧，把a3拉进来，，
接下来，距离a1a2a3最近的就是a4了，
本人绘图能力有限，之后同理可得~~~
可见如果存在边相同的情况，最小生成树可能是不同的（但其总权值相同）（为什么？？都是贪心得到的噻~~）
讲到这里估计你也搞懂prim算法的基本原理了，
如何实现呢？？？？？？
边的储存，，随你啦，一般是邻接矩阵or邻接表
邻接矩阵就是一个n*n的数组，p[i][j]就是i-j的长度
邻接表就是一个链表，每个节点储存了这条边的起点终点，长度，以及上一条边的位置
（为什么不储存下一条边的位置？？因为插入边的时候还得找到上一条边，即使再加个数组实时记录每个点最新边的位置，
也还要一个数组记录每个点最老边的位置，如果储存上一条边就没这么麻烦了）
PS:边太多不好哦~~=。=
储存好了，，就开始扫把，
从第一个点开始，扫到最短相邻边，记录边长，把点标记为已走，然后把与该点相邻且终点未走的边拉进来，
再扫到最短边，在拉进来…………
当然，如果你还嫌时间慢的话~~~
那就优化吧：建一个堆，扫一次就把边放进去~~，取得时候判断有没有到达过，到过就继续取，没到过就走这条路啦！！~~
不过貌似建堆的代码挺长的额。。。=。=
也有另一种思路（仅供大家参考啊~~刚想到的~~ =。= ）：对每个点的相邻边按大小排序（终点得跟着动啊~~~），
新建一个数组 p[MAX] 记录每个点周围的边中 已走的个数，（就是已走到的位置），
然后同样取边，第i个点的边取到了，那么p[i]++，寻求集合周围最大边时，
就只要从每个点周围的ROAD[i][ p[i]+1 ] （邻接矩阵） 中找就行了，
找的时候，如果这条边是不可走的（终点走过），那就更新一下这个点的周围已走，相比朴素算法好多了，
相比堆也相差无几，而且可行性也略好，不过本屌没试过~~~
基本思想讲完了。。
prim是基于点扫描的算法，点少边多的时候可以用一用（为什么？它每个点只扫一遍啊。 =。 =）
有时候点多边少。。就得用另一种算法~~~kruskal算法，这个以后再讲~~~
附上刚写的代码一段~~~（朴素算法~~）
int prim()
{
int ans = 0;
int dist[n+1];
bool vis[n+1];
for (int i = 1; i <= n; i++)
{//将所有点距1点的距离更新，，标记所有点未走
vis[i] = false;
if ( road[1][i] != 0 )
{
dist[i] = road[1][i];
}
else
{
dist[i] = 99999;//很大很大
}
}
dist[1] = 0;//设第一个点未走。。。
for (int i = 1; i <= n; i++)//没走一次拉入一个点，没有把1号特殊处理=。=
{
int mini = 99999;
int end = 0;//mini是记录最小值的，end是记录终点
for (int j = 1; j <= n; j++)
{//寻找最短路
if ( vis[j] == false && mini > dist[j] )
{
mini = dist[j];
end = j;
}
}
vis[end] = true;//标记已走
ans += mini;//更新长度
for (int j = 1; j <= n; j++)
{//更新周边点的最短路径
if ( road[end][j] != 0 && road[end][j] < dist[j] )
{
dist[j] = road[end][j];
}
}
}
return ans;
}
虽然有点丑陋啊~~而且正确性也无法考证。。。=。=
有的时候点多边少~~prim就不适合了
讲完了
大牛勿喷。。。
=。=
----------------------------------END