1．算法思想：
图采用邻接矩阵存储，贪心找到目前情况下能连上的权值最小的边的另一端点，加入之，直到所有的顶点加入完毕。
2．算法实现步骤：
设图G =（V，E），其生成树的顶点集合为U。
（1）把v0放入U。
（2）在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
（3）把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
最后得到最小生成树U=<V,TE>，其中TE为最小生成树的边集。
其算法的时间复杂度为O(n^2)。
3．算法的关键与优化：
我们很容易就可以发现prim算法的关键：每次如何从生成树T到T外的所有边中，找出一条最小边。例如，在第k次前，生成树T中已有k个顶点和（k-1）条边，此时，T到T外得所有边数为k*（n-k）,当然，包括没有边的两顶点，我们记权值为“无穷大”的边在内，从如此多的边中查找最短边，时间复杂度为O(k(n-k))，显然无法满足我们的期望。
我们来看O(n-k)的方法：假定在进行第k次前已经保留着从T中到T外的每一个顶点（共n-k个）的各一条最短边，在进行第k次时，首先从这（n-k）条最短边中，找出一条最最短边（它就是从T到T外的最短边），假设为（vi,vj），此步需要进行（n-k）次比较；然后把边（vi,vj）和顶点vj并入T中的边集TE和顶点集U中，此时，T外只有n-(k+1)个顶点，对于其中的每个顶点vt，若（vj,vt）边上的权值小于原来保存的从T中到vt的最短边的权值，则用（v,vt）修改之，否则，保持原最小边不变。这样就把第k次后T中到T外的每一个顶点vt的各一条最短边都保留下来了，为第(k+1)次最好了准备。这样Prim的总时间复杂度为O(n^2)。
进一步优化，每次要寻找集合内外连接的最小值，可以用堆或优先队列最小值时间复杂度为o(longn),总时间复杂度为n(nlongn).
代码：
void prim(){ bool vis[maxn];//集合内外的标志 int cost[maxn];//存储集合内到集合外顶点的最小值 int i,j,minc,next,ans=0;//next最小值对应的顶点. memset(vis,0,sizeof(vis)); memset(cost,0x3f,sizeof(cost)); cost[1]=0;//初始化起始顶点1的花费.从任何一个顶点开始都可以; for(i=1;i<=n;i++){ minc=0x3f3f3f3f; for(j=1;j<=n;j++) //找出集合内外连接的最短距离,和所连接的顶点mini; if (!vis[j]&& cost[j]<minc) { minc=cost[j]; next=j; } vis[next]=true; //选中顶点j并入集合内 for (j=1;j<=n;j++)//更新集合内集合外最短距离数组cost; if ((!vis[j]&& cost[j]<map [next][j]) cost[j]=map [next][j] } return ; }