‘壹’ prim算法不是很理解啊
其实它就是一个贪心
不知道你学过dijkstra没有，这两个是很类似的（代码上也是，朴素实现好象就差1句）。
如果点A是未加入树中最近的那个点，那么我们贪心地加入A肯定是最优的！
假设B是任意一个未加入树中不是最近的点，而我们这次加入了B。
那么接下来可能有两种情况再加入A：
1、直接加入A，这跟我们直接加入A是一样的，但我们不能保证当时加入B是最优的。
2、用B更新边后加入A，但是A比B要离树近，所以之前加入A，再用A更新B然后加入B要比这种情况更优。
综上，我们每次加入A总是最优的！
所以prim是对的。
‘贰’ Prim算法，求大牛通俗易懂地解释下为什么成立。。。
prim算法就是把点分成两个集合，一个集合里面包含已经加入生成树的点，另一个包含未加入的，然后不断在两个集合之间找最短的边，直到所有的点都加入到生成树中，这时候就构成了最小生成树。
‘叁’ KRUSKAL算法和PRIM算法
不是吧，网络白科里面有这俩个算法的详细的讲解，你可以去查查
‘肆’ 利用Prim（普里姆）算法 构造最小生成树 程序
算法同样是解决最小生成树的问题。
其算法为：在这n个点中的相通的边进行排序，然后不断地将边添加到集合中（体现了贪心的算法特点），在并入集合之前，必须检查一下这两点是不是在一个集合当中，这就用到了并查集的知识。直到边的集合达到了n-1个。
与prim算法的不同：prim算法为单源不断寻找连接的最短边，向外扩展，即单树形成森林。而Kruskal算法则是不断寻找最短边然后不断将集合合并，即多树形成森林。
复杂度的不同：prim算法的复杂度是O(n^2),其中n为点的个数。Kruskal算法的复杂度是O(e*loge)，其中e为边的个数。两者各有优劣，在不同的情况下选择不同的算法。
Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
Prim算法实现：
（1）集合：设置一个数组set(i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
{先选定一个点，然后从该点出发，与该点相连的点取权值最小者归入集合，然后再比较在集合中的两点与其它各点的边的权值最小者，再次进入集合，一直到将所有的点都归入集合为止。}
‘伍’ prim算法是基于什么原理
贪心
具体证明可以看《算法导论》最小生成树那章
‘陆’ 什么是Prim算法
Prim算法
Prim算法用于求无向图的最小生成树
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
Prim算法实现：
（1）集合：设置一个数组set[i](i=0,1,..,n-1),初始值为 0,代表对应顶点不在集合中（注意：顶点号与下标号差1）
（2）图用邻接阵表示，路径不通用无穷大表示，在计算机中可用一个大整数代替。
参考程序
/* Prim.c
Copyright (c) 2002, 2006 by ctu_85
All Rights Reserved.
*/
/* The impact of the situation of articulation point exists can be omitted in Prim algorithm but not in Kruskal algorithm */
#include "stdio.h"
#define maxver 10
#define maxright 100
int main()
{
int G[maxver][maxver],in[maxver]=,path[maxver][2];
int i,j,k,min=maxright;
int v1,v2,num,temp,status=0,start=0;
restart:
printf("Please enter the number of vertex(s) in the graph:\n");
scanf("%d",&num);
if(num>maxver||num<0)
{
printf("Error!Please reinput!\n");
goto restart;
}
for(j=0;j<num;j++)
for(k=0;k<num;k++)
{
if(j==k)
G[j][k]=maxright;
else
if(j<k)
{
re:
printf("Please input the right between vertex %d and vertex %d,if no edge exists please input -1:\n",j+1,k+1);
scanf("%d",&temp);
if(temp>=maxright||temp<-1)
{
printf("Invalid input!\n");
goto re;
}
if(temp==-1)
temp=maxright;
G[j][k]=G[k][j]=temp;
}
}
for(j=0;j<num;j++)
{
status=0;
for(k=0;k<num;k++)
if(G[j][k]<maxright)
{
status=1;
break;
}
if(status==0)
break;
}
do
{
printf("Please enter the vertex where Prim algorithm starts:");
scanf("%d",&start);
}while(start<0||start>num);
in[start-1]=1;
for(i=0;i<num-1&&status;i++)
{
for(j=0;j<num;j++)
for(k=0;k<num;k++)
if(G[j][k]<min&&in[j]&&(!in[k]))
{
v1=j;
v2=k;
min=G[j][k];
}
if(!in[v2])
{
path[i][0]=v1;
path[i][1]=v2;
in[v1]=1;
in[v2]=1;
min=maxright;
}
}
if(!status)
printf("We cannot deal with it because the graph is not connected!\n");
else
{
for(i=0;i<num-1;i++)
printf("Path %d:vertex %d to vertex %d\n",i+1,path[i][0]+1,path[i][1]+1);
}
return 1;
}
Prim算法。
设图G =（V，E），其生成树的顶点集合为U。
①、把v0放入U。
②、在所有u∈U，v∈V-U的边(u，v)∈E中找一条最小权值的边，加入生成树。
③、把②找到的边的v加入U集合。如果U集合已有n个元素，则结束，否则继续执行②。
其算法的时间复杂度为O(n^2)
参考程序
//Prim 算法 读入顶点数(n)、边数(m)，边的起始点和权值 用邻接矩阵储存
//例如
//7 12 (7个顶点12条边)
//1 2 2
//1 4 1
//1 3 4
//2 4 3
//2 5 10
//3 4 2
//4 5 7
//3 6 5
//4 6 8
//4 7 4
//5 7 6
//6 7 1
#include <stdio.h>
#include <string.h>
int main()
{
int m , n;
int a[201][201] , mark[201] , pre[201] , dist[201];
int s , t , w;
int i , j , k , min , tot;
freopen("Prim.txt" , "r" , stdin);
//读入数据
memset(a , 0 , sizeof(a));
scanf("%d %d" , &n , &m);
for (i = 0; i < m; i ++)
{
scanf("%d %d %d" , &s , &t , &w);
a[s][t] = w; a[t][s] = w;
}
//赋初值
memset(mark , 0 , sizeof(mark));
memset(pre , 0 , sizeof(pre));
memset(dist , 9999 , sizeof(dist));
dist[1] = 0;
//Prim
for (i = 1; i <= n; i ++)
{
min = 9999; k = 0;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (dist[j] < min)) {min = dist[j]; k = j;}
if (k == 0) break;
mark[k] = 1;
for (j = 1; j <= n; j ++)
if ((mark[j] == 0) && (a[k][j] < dist[j]) && (a[k][j] > 0))
{
dist[j] = a[k][j];
pre[j] = k;
}
}
tot = 0;
for (i = 1; i <= n; i ++) tot += dist[i];
printf("%d\n" , tot);
return 0;
}
‘柒’ Prim算法，解释一步就好！
到C时可以得到的结果是：到2的最短长度为5，到5的最短长度为6，所以选最小的那个长度为5，即选择下一个连接节点为2，即得到了D图
‘捌’ 根据PRIM算法构造最小生成树怎么确定出发点
用pascal语言的，可以转成C++很容易的
首先定义数据类型:
type adjmatrix=array [1．.n,1..n] of real;
//定义一个n＊n的矩阵类型adjmatrix,以便存储邻接矩阵//
edge=record
beg,en:1..n;
length:real;
end;
//定义边的存储结构为edge,其中beg是边的起点, en 是边的终点,length是边的权值//
treetype=array [1..n－1] of edge;
//定义一个基类型为edge的数组类型 treetype,其元素个数为n－1个//
var net:adjmatrix;
//定义一个adjmatrix类型的变量net,图的邻接矩阵就存放在net中//
tree:treetype;
//定义一个treetype类型的变量tree,tree中可以存放n－1条边的信息，包括起点、终点及权值。在算法结束后，最小生成树的n－1 条边就存放在tree中//
算法如下(设n为构造的出发点)：
procere prim(net:adjmatrix;var tree:treetype);
//过程首部.参数的含义是:值参数net传递图的邻接矩阵,变参tree指明最小生成树的存放地址//
begin
for v:=1 to n－1 do
//此循环将顶点n与图中其它n－1个顶点形成的n－1条边存放在变量tree中//
[tree[v].beg:=n;
tree[v].en:=v;
tree[v].length:=net[v]]
for k:=1 to n－1 do
//此循环执行算法思想中的步骤2,循环体每执行一次,TE中将增加一条边,在算法中,这条增加的边存放在变量tree中的第k个元素上,可以这样认为,tree中从第1到第k号元素中存放了TE和U的信息。注意:在算法思想中我们特别提醒了TE和U的动态性,表现在算法中,这种动态性 体现在循环变量k的变化上。//
[min:=tree[k].length;
for j:=k to n－1 do
if tree[j].length<min then
[min:=tree[j].length;
m:=j;]
//上面两条语句用于搜索权值最小的边//
v:=tree[m].en;
//此语句记录刚加入TE中的边的终点,也即即将加入U中的顶点//
edge:=tree[m];
tree[m]:=tree[k];
tree[k]:=edge;
//上面三句用于将刚找到的边存储到变量tree的第k号元素上//
for j:=k＋1 to n－1 do
//此循环用于更新tree中第k＋1到第n－1号元素。更新以后这些元素中的en子项是各不相同的,它们的全部就是集合V－U;beg子项则可以相同,但它们需满足两个条件:一是应属于集合U;另一是beg子项和en子项行成的边,在所有与顶点en联系的边中权值应最小。//
[d:=net[v.tree[j].en];
if d<tree[j].length
then [tree[j].length:=d;
tree[j].beg:=v;]
]
]
for j:=1 to n－1 do
//此循环用于输出最小生成树//
writeln(tree[j].beg,tree[j].en,tree[j].length);
end;
‘玖’ Prim算法的实现过程
G=（V,E）
①初始化：读入的数据用邻接矩阵x存储，一个一维布尔型数组chosen，记录第i个节点是否已选，初始值除1外全部设为false，记录权值的变量cost赋值为0；
以下②到④循环执行v-1次（每次生成一条边，运行（点的个数减1）次后，生成一棵最小生成树）：
②临时变量p赋值为无限大，用于记录当前最小值；
③二重循环（外循环i，内循环j）扫描邻接矩阵：如果chosen[i]=true（也就是说第i个点已选），那么扫描x[i]，如果not(chosen[j])（也就是说第j个点未选），那么如果x[i,j]<p，那么p赋值为x[i,j],临时变量q赋值为j;
④把cost赋值为cost+o，把chosen[q]赋值为true（也就是说第j个点已选）；
⑤输出cost。
一、以上给出具体的运行过程。这个算法的策略就是贪心，和dijkstra差不多，每次都选择未选的边中权值最小的那一条，直到生成最小生成树。用chosen的目的就是保证生成过程中没有环出现，也就是说保证选择的边不会通向一个已经包含在生成树中的点。
二、这个只输出最小生成树的每条边权值之和，如果要输出整棵最小生成树，加一个[1..n,1..2]的数组，在第④步的时候把每次选的边记录下来就可以了。
三、用小顶堆在第③步优化一下的话就不用每次都扫描那么多边了，只不过建堆维护堆代码写起来很麻烦。
四、prim适合用于比较稠密的网，点数和边数差不多的时候效率很恶心，一般都用kruskal。
‘拾’ 数据结构（prim算法）
开始时将v1加入U后，更新ee中的值应该是0 6 1 2 无穷 无穷；
将v3加入U后，更新ee中的值应该是0 5 0 2 6 4；
怎么会出现你说的0 6 0 5 无穷无穷的情况呢？
for(j = 0;j < G.vexnum;j++)中不是有条件判断么，要在k到j的距离小于ee[j]的value值时才会更新ee[j]啊。