导航:首页 > 源码编译 > 普里姆算法图

普里姆算法图

发布时间:2024-11-03 17:52:14

⑴ 普里姆算法的普里姆算法的实现

为了便于在两个顶点集U和V-U之间选择权最小的边,建立了两个辅助数组closest和lowcost,它们记录从U到V-U具有最小权值的边,对于某个j∈V-U,closest[j]存储该边依附的在U中的顶点编号,lowcost[j]存储该边的权值。
为了方便,假设图G采用邻接矩阵g存储,对应的Prim(g,v)算法如下:
void Prim(MatGraph g,int v) //输出求得的最小生树的所有边
{ int lowcost[MAXVEX]; //建立数组lowcost
int closest[MAXVEX]; //建立数组closest
int min,i,j,k;
for (i=0;i<g.n;i++) //给lowcost[]和closest[]置初值
{ lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for (i=1;i<g.n;i++) //构造n-1条边
{ min=INF; k=-1;
for (j=0;j<g.n;j++) //在(V-U)中找出离U最近的顶点k
if (lowcost[j]!=0 && lowcost[j]<min)
{ min=lowcost[j];
k=j; //k为最近顶点的编号
}
printf( 边(%d,%d),权值为%d ,closest[k],k,min);
lowcost[k]=0; //标记k已经加入U
for (j=0;j<g.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;
}
}
}
普里姆算法中有两重for循环,所以时间复杂度为O(n2),其中n为图的顶点个数。由于与e无关,所以普里姆算法特别适合于稠密图求最小生成树。

⑵ 最小生成树 普里姆算法有问

普里姆算法构造最小生成树算法的思想是:选择一个结点,然后从这个结点开始,选择权值最小的边,用一条边连接,然后再以前面的那个结点开始,和你连接的那个结点作为根节点,再选择权值最小的边进行连接。
对权值给出解释:以上图为例,权值就是你第一个图那几条边(弧)上,所标的数字。
对楼主所提出的问题:并不是连接那圆圈中最小的圆圈,如果没错的话,那圆圈中的数字表示的是V1---V6六个顶点,并不是代表数字,以3和6为顶点,找权值最小边,显然6——4为最小,即权值为2,顶点364相连接的时候各以364为顶点寻找最小边,应该先从6连接到2,那么现在加入顶点的为3642顶点,现在以3642为顶点寻找最小边,应该从2连接到1,现在被连接的有63421,在以63421为顶点寻找最小边
出现了问题:如果以5为权值的话,无论从2连接到4还是从3连接到4都出现了环,当然我们知道数中是不能出现环的,所以寻找次小的,剩余5与13之间权值最小为13.所以将1连接5,即得到最小生成树。
楼主可以按照我说的在纸上画一下试试
从6连接到3因为有前提条件:从顶点V3开始用普里姆方法求其最小生成数,可见是从顶点3连接到6,而不是从6连接到3
希望可以解决楼主的疑惑,谢谢!

⑶ 锲炬墍绀烘槸涓涓镞犲悜甯︽潈锲,璇峰垎鍒鎸埘rim绠楁硶鍜孠ruskal绠楁硶姹傛渶灏忕敓鎴愭爲.

•鏅閲屽嗭纸Prim锛夌畻娉

锘烘湰镐濇兂

锅囱綨=(V,E)鏄涓涓鍏锋湁n涓椤剁偣镄勮繛阃氱绣锛孴=(U,TE)鏄镓姹傜殑链灏忕敓鎴愭爲锛屽叾涓璘鏄疶镄勯《镣归泦锛孴E鏄疶镄勮竟闆嗐

锛1锛夊埯濮婾={u0}(u0鈭圴),TE=蠁锛

锛2锛夊湪镓链塽鈭圲,v鈭圴-U镄勮竟涓阃変竴𨱒′唬浠锋渶灏忕殑杈癸纸u0锛寁0锛夊苟鍏ラ泦钖圱E锛屽悓镞跺皢v0骞跺叆U锛

锛3锛夐吨澶嶏纸2锛夛纴鐩村埌U=V涓烘銆

姝ゆ椂锛孴E涓蹇呭惈链塶-1𨱒¤竟锛屽垯T=锛圴锛寋TE}锛変负N镄勬渶灏忕敓鎴愭爲銆

娉ㄦ剰锛1.链灏忕敓鎴愭爲涓嶅敮涓銆

2.璇ュ浘浠庤妭镣规渶灏忓紑濮嬨

⑷ 利用普里姆算法求解最小生成树,写出步骤或画图表示过程。

<1,6>边长度未知,这里看成无穷大。
历次循环中,选择两端点分别在U,V中的边中长度最小者,
具体如下:
1. 将1加入U中,其余点加入V中。
2. 选择边<1,7>,将7加入U中,从V中除去该点。
3. 选择边<7,6>,将6加入U中,从V中除去该点。
4. 选择边<1,2>,将2加入U中,从V中除去该点。
5. 选择边<2,3>,将3加入U中,从V中除去该点。
6. 选择边<2,4>,将4加入U中,从V中除去该点。
7. 选择边<2,5>,将5加入U中,从V中除去该点。
结束。由上述六条边组成的树为求得的最小生成树。

⑸ 什么是普利姆算法

Prim算法:是图的最小生成树的一种构造算法。

假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,TV 是 WN 上最小生成树中顶点的集合,TE 是最小生成树中边的集合。显然,在算法执行结束时,TV=V,而 TE 是 E 的一个子集。在算法开始执行时,TE 为空集,TV 中只有一个顶点,因此,按普里姆算法构造最小生成树的过程为:在所有“其一个顶点已经落在生成树上,而另一个顶点尚未落在生成树上”的边中取一条权值为最小的边,逐条加在生成树上,直至生成树中含有 n-1条边为止。

如果看不懂还可以找一本数据结构的书看,这个算法挺简单的。

btw:其实你有空问,应该有空网络啊~网络就有了。懒得写,我还是直接从网络过来的~

⑹ prim算法是什么

prim算法是图论中的一种算法。

普里姆算法(Prim算法),图论中的一种算法,可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中,不但包括了连通图里的所有顶点(英语:Vertex (graph theory)),且其所有边的权值之和亦为最小。

简介

最小生成树是数据结构中图的一种重要应用,它的要求是从一个带权无向完全图中选择n-1条边并使这个图仍然连通(也即得到了一棵生成树),同时还要考虑使树的权最小。

为了得到最小生成树,人们设计了很多算法,最着名的有prim算法和kruskal算法。教材中介绍了prim算法,但是讲得不够详细,理解起来比较困难,为了帮助大家更好的理解这一算法,本文对书中的内容作了进一步的细化,希望能对大家有所帮助。

⑺ 用普里姆算法构造如图所示的图G的一棵最小生成树。

解:使用普里姆算法构造出如下图G的一棵最小生成树。

阅读全文

与普里姆算法图相关的资料

热点内容
游戏运行文件解压到哪个盘 浏览:119
银行业务程序员要注意什么 浏览:390
怎么看压缩机牌子的 浏览:900
安卓手机怎么设置网址黑名 浏览:311
女超人全在哪个App可以看 浏览:393
可乐优品app图标长什么样子 浏览:870
iphone米家app怎么扫码 浏览:575
servqual具体算法 浏览:287
怎么在app关闭闪付 浏览:456
一个压缩文件能解压多久 浏览:573
如何在光遇中知道自己被拉黑安卓 浏览:664
c跨平台开发技术指南pdf 浏览:546
算法分析师就业人数图 浏览:820
安卓手机相册为什么看不到照片 浏览:328
linux如何更新python版本 浏览:359
pdf文件打马赛克 浏览:60
模板提高编译速度 浏览:146
ppt硬核训练营解压密码 浏览:584
恒智天成软件识别不到加密狗 浏览:358
天和日历速算法 浏览:213