- 1、本文档共26页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
详解图的应用(最小生成树、拓扑排序、关键路径、最短路径)
这篇文章主要介绍了图的应用(最小生成树、拓扑排序、关键路径、最短路径),需要的朋友可以参考下
1.最小生成树:无向连通图的所有生成树中有一棵边的权值总和最小的生成树
1.1 问题背景:假设要在n个城市之间建立通信联络网,则连通n个城市只需要n—1条线路。这时,自然会考虑这样一个问题,如何在最节省经费的前提下建立这个通信网。在每两个城市之间都可以设置一条线路,相应地都要付出一定的经济代价。n个城市之间,最多可能设置n(n-1)/2条线路,那么,如何在这些可能的线路中选择n-1条,以使总的耗费最少呢?
1.2 分析问题(建立模型):
可以用连通网来表示n个城市以及n个城市间可能设置的通信线路,其中网的顶点表示城市,边表示两城市之间的线路,赋于边的权值表示相应的代价。对于n个顶点的连通网可以建立许多不同的生成树,每一棵生成树都可以是一个通信网。即无向连通图的生成树不是唯一的。连通图的一次遍历所经过的边的集合及图中所有顶点的集合就构成了该图的一棵生成树,对连通图的不同遍历,就可能得到不同的生成树。
图 G5无向连通图的生成树 为(a)、(b)和(c)图所示:
G5
G5的三棵生成树:
可以证明,对于有n 个顶点的无向连通图,无论其生成树的形态如何,所有生成树中都有且仅有n-1 条边。
1.3最小生成树的定义:
如果无向连通图是一个网,那么,它的所有生成树中必有一棵边的权值总和最小的生成树,我们称这棵生成树为最小生成树,简称为最小生成树。
最小生成树的性质:假设N=(V,{ E}) 是个连通网,U是顶点集合V的一个非空子集,若(u,v)是个一条具有最小权值(代价)的边,其中,
则必存在一棵包含边(u,v)的最小生成树。
1.4 解决方案:
两种常用的构造最小生成树的算法:普里姆(Prim)和克鲁斯卡尔(Kruskal)。他们都利用了最小生成树的性质
1.普里姆(Prim)算法:有线到点,适合边稠密。时间复杂度O(N^2)
假设G=(V,E)为连通图,其中V 为网图中所有顶点的集合,E 为网图中所有带权边的集合。设置两个新的集合U 和T,其中
集合U(顶点集) 用于存放G 的最小生成树中的顶点,
集合T (边集合)存放G 的最小生成树中的边。
T ,U的初始状态:令集合U 的初值为U={u1}(假设构造最小生成树时,从顶点u1 出发),集合T 的初值为T={}。
Prim 算法的思想是:从所有u∈U,v∈V-U 的边中,选取具有最小权值的边(u,v)∈E,将顶点v 加入集合U 中,将边(u,v)加入集合T 中,如此不断重复,直到U=V 时,最小生成树构造完毕,这时集合T 中包含了最小生成树的所有边。
Prim 算法可用下述过程描述,其中用wuv 表示顶点u 与顶点v 边上的权值。(1)U={u1},T={};(2)while (U≠V)do(u,v)=min{wuv;u∈U,v∈V-U }T=T+{(u,v)}U=U+{v}(3)结束。按照Prim 方法,从顶点1 出发,该网的最小生成树的产生过程如图:
为实现Prim 算法,需设置两个辅助closedge,用来保存U到集合V-U 的各个顶点中具有最小权值的边的权值。对每个Vi∈(V-U )在辅助数组中存在一个相应的分量closedge[i-1],它包括两个域:
typedef struct ArcNode
{
int adjvex; //adjex域存储该边依附的在U中的顶点VrType lowcost; //lowcost域存储该边上的权重}closedge[MAX_VERTEX_NUM];
显然:
初始状态时,U={v1}(u1 为出发的顶点),则到V-U 中各项中最小的边,即依附顶点v1的各条边中,找到一条代价最小的边(u0,v0)= (1,3)为生成树上一条边。同时将v0(=v3)并入集合U中。然后修改辅助数组的值。
1)将closedge[2].lowcost = 0;//表示顶点V3三已经并入U
2) 由于边(v2,v3)的权值小于closedge[1].lowcost,故需修改closedge[1]为边(v2,v3)及其权值,同理修改closedge[4],closedge[5].
closedge[1].adjvex = 3.
closedge[1].lowcost = 5.
closedge[4].adjvex = 1.
closedge[4].lowcost = 5.
closedge[5].adjvex = 3.
closedge[5].lowcost = 6.
以此类推,直至U = V;
下图给出了在用上述算法构造网图7.16的最小生成树的过程中:
Prim 算法实现
您可能关注的文档
- 网上食品商店的设计与实现毕业论文讲述.doc
- 通信接口与通信协议详解.ppt
- 通信系统应急预案详解.docx
- 网易企业邮箱与AD域帐号同步系统说明文档讲述.doc
- 网易视频云分享:HBase–探索HFile索引机制讲述.docx
- 网上景区方案V.01讲述.ppt
- 通信原理_绪论详解.ppt
- 透层试验段施工方案详解.doc
- 网格案例题讲述.doc
- 辽宁省实验中学等五校2014-2015学年高二化学下学期期末考试试题详解.doc
- 10《那一年,面包飘香》教案.docx
- 13 花钟 教学设计-2023-2024学年三年级下册语文统编版.docx
- 2024-2025学年中职学校心理健康教育与霸凌预防的设计.docx
- 2024-2025学年中职生反思与行动的反霸凌教学设计.docx
- 2023-2024学年人教版小学数学一年级上册5.docx
- 4.1.1 线段、射线、直线 教学设计 2024-2025学年北师大版七年级数学上册.docx
- 川教版(2024)三年级上册 2.2在线导航选路线 教案.docx
- Unit 8 Dolls (教学设计)-2024-2025学年译林版(三起)英语四年级上册.docx
- 高一上学期体育与健康人教版 “贪吃蛇”耐久跑 教案.docx
- 第1课时 亿以内数的认识(教学设计)-2024-2025学年四年级上册数学人教版.docx
文档评论(0)