最小生成树prim算法
❶ 最小生成树两种算法有何区别
主要有两个：
1.普里姆（Prim)算法
特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法
特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。
❷ prim和kruscal算法得到的最小生成树是否一样
应该不一样。可以用一个图根据两算法试一下，若一样，再修改图，之后应该就可以了。
（网络或者查书本更加有效……）
构造G的最小生成树的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且c[i][j]最小的边，将顶点j添加到S中。
这个过程一直进行到S=V时为止。
Kruskal算法构造G的最小生成树：将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v, w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v, w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止
❸ 急！数据结构最小生成树prim算法C语言实现
Kruskal算法：
void Kruskal(Edge E[],int n,int e)
{
int i,j,m1,m2,sn1,sn2,k;
int vset[MAXE];
for (i=0;i<n;i++) vset[i]=i; //初始化辅助数组
k=1; //k表示当前构造最小生成树的第几条边,初值为1
j=0; //E中边的下标,初值为0
while (k<n) //生成的边数小于n时循环
{
m1=E[j].u;m2=E[j].v; //取一条边的头尾顶点
sn1=vset[m1];sn2=vset[m2]; //分别得到两个顶点所属的集合编号
if (sn1!=sn2) //两顶点属于不同的集合,该边是最小生成树的一条边
{
printf(" (%d,%d):%d/n",m1,m2,E[j].w);
k++; //生成边数增1
for (i=0;i<n;i++) //两个集合统一编号
if (vset[i]==sn2) //集合编号为sn2的改为sn1
vset[i]=sn1;
}
j++; //扫描下一条边
}
}
Prim算法：
void prim(MGraph g,int v)
{
int lowcost[MAXV],min,n=g.vexnum;
int closest[MAXV],i,j,k;
for (i=0;i<n;i++) //给lowcost[]和closest[]置初值
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<n;i++) //找出n-1个顶点
{
min=INF;
for (j=0;j<n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{
min=lowcost[j];k=j;
}
printf(" 边(%d,%d)权为:%d/n",closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<n;j++) //修改数组lowcost和closest
if (g.edges[k][j]!=0 && g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];closest[j]=k;
}
}
}
❹ 利用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算法），图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。
简介橘尘
最小生成树是数据结构中图的一种重要应用，它的要求是从一个带权无向完全图中选择n－1条边并使这个图仍然连通（也即得到了一棵生成树）,同时还要考虑使树的权最小。
为了得到最小生成树，人们设计了很多算法，最着名的有prim算法和kruskal算法。教材中介绍了prim算法，但是讲得不够详细，理解起来比较困难，为了帮助大家更好的理解这一算法，仔升本文对书圆戚禅中的内容作了进一步的细化，希望能对大家有所帮助。