数据结构与算法-第六章 图的最小生成树
admin
2024-04-02 08:51:16
0

概念回顾:生成树

设图G=(V, E)是一个连通图,当从图中任一顶点出发遍历图G时,将边集E(G)分成两个集合T(G)和B(G).其中T(G)是遍历图时所经过的边的集合,B(G)是遍历图时未经过的边的集合.显然G1(V, T)是图G的极小连通子图.即子图G1是连通图G的生成树.

所有顶点均由边链接在一起,但不存在回路的图称为生成树;
一个图可以有许多棵不同的生成树;

所有生成树具有以下共同特点:
------生成树的顶点个数与图的顶点个数相同;
------生成树是图的极小连通子图,去掉一条边则非连通;
------一个有n个顶点的连通图的生成树有n-1条边;
------在生成树中再加一条边必然形成回路;
------生成树中任意两点连的路径是惟一的;

含有n个顶点n-1条边的图不一定是生成树

最小生成树

给定一个无向网络,在该网的所有生成树中,使得各边权值之和最小的那棵生成树称为最小生成树,也叫最小代价生成树

构造最小生成树

构造最小生成树的算法有很多,其中多数都利用了MST的性质

MST性质:

设N=(V, E)是一个连通网,U是顶点集V的一个非空子集.若边(u, v)是一条具有最小权值的边,其中u∈U,v∈V-U
,则必存在一棵包含边(u, v)的最小生成树
通俗的来说就是在连通图中的最小权值的边必在一棵最小生成树中包含着在生成树的构造过程中,图中n个顶点分属两个集合:已落在生成树上的顶点集合:U尚未落在生成树上的顶点集合:V-U
接下来则应在所有连通U中顶点和V-U中顶点的边中选取权值最小的边
普利姆(Prim)算法
设N=(V, E)是连通图,TE是N上最小生成树中边的集合;
初始令U=(u1),(u1∈V),TE={};
在所有u∈U,v∈V-U的边(u, v)∈E中,找一条代价最小的边(u1,v1);
将(u1,v1)并入集合TE中,同时v1并入U;
重复上述操作,直至U=V为止,则T=(V, TE)为N的最小生成树;
克鲁斯卡尔(Kruskal)算法
设连通网N=(V, E),令最小生成树初始状态为只有n个顶点而无边的非连通图T=(V, {}).每个顶点自成一个连通分量;
在E中选取代价最小的边,若该边依附的顶点落在T中不同的连通分量上(即不能形成环),则将此边加入到T中;否则,舍去此边,选取下一条代价最小的边;
依次类推,直至T中所有顶点都在同一连通分量中为止
两种算法比较
算法名		普利姆算法		克鲁斯卡尔算法算法思想		选择点			选择边时间复杂度	O(n^2)			O(eloge)n为顶点数		e为边数
适应范围		稠密图			稀疏图

相关内容

热门资讯

安卓 代替系统音效设置,打造个... 你有没有发现,手机里的那些系统音效有时候真的让人有点烦躁呢?比如那个每次接电话时“叮咚”一声,或者是...
安卓系统整体性,构建移动设备的... 你知道吗?在智能手机的世界里,安卓系统就像是个全能的魔术师,它不仅拥有丰富的魔法,还能让各种神奇的魔...
安卓系统能玩鬼泣么?,畅享动作... 你有没有想过,在安卓系统上玩《鬼泣》这款游戏会是怎样的体验呢?没错,就是那个让你热血沸腾、挑战极限的...
安卓系统手机编曲软件,音乐创作... 你有没有想过,用手机也能轻松编曲?没错,就是那个你每天不离手的安卓系统手机!现在,我就要给你揭秘几款...
车载导航显示安卓系统,车载导航... 你有没有发现,现在的车载导航系统越来越智能了?尤其是那些搭载了安卓系统的车载导航,简直就像是个贴心的...
安卓系统启动黑屏,安卓系统启动... 手机屏幕突然黑了,这可怎么办?别急,今天就来和你聊聊安卓系统启动黑屏这个让人头疼的问题。你知道吗,这...
怎么解除订阅安卓系统,安卓系统... 你是不是也和我一样,手机里订阅了好多服务,结果现在想解除订阅,却一头雾水?别急,今天就来手把手教你如...
安卓系统停用怎么开启,轻松恢复... 亲爱的手机控们,你是否曾经遇到过安卓系统突然停用的情况,让你手忙脚乱,不知所措?别担心,今天就来教你...
安卓系统电池健康度,电池健康度... 你有没有发现,你的安卓手机最近是不是有点儿不给力了?电池续航能力大不如前,充电速度也慢了不少?别急,...
安卓系统按键怎么截图,安卓系统... 你是不是也和我一样,有时候想截个图分享给朋友,却发现安卓手机的截图功能有点神秘呢?别急,今天就来手把...
购票系统安卓源代码,架构设计与... 你有没有想过,那些我们每天离不开的购票系统,它们背后的秘密是什么呢?今天,就让我带你一探究竟,揭开购...
安卓手机系统后台测试,深度解析... 你有没有发现,你的安卓手机后台总是悄悄地忙碌着?别小看了这些后台程序,它们可是手机系统稳定运行的关键...
安卓系统重启的图标,解锁设备新... 手机突然重启,是不是心里有点慌?别急,今天就来和你聊聊安卓系统重启的图标,让你一眼就能认出它,再也不...
车载智慧屏安卓系统,智能出行新... 你有没有发现,现在的车载智慧屏越来越智能了?尤其是那些搭载了安卓系统的,简直就像是个移动的小电脑,不...
安卓系统连上网权限,解锁设备无... 你有没有发现,你的安卓手机里有些应用总是偷偷连上网?别小看这个小小的网络权限,它可是能影响你隐私、消...
安卓谷歌操作系统,探索安卓谷歌... 你知道吗?在智能手机的世界里,有一个操作系统可是无人不知、无人不晓,那就是安卓谷歌操作系统。它就像一...
安卓系统手写%怎样调出,具体实... 你有没有遇到过这种情况:在使用安卓手机的时候,突然想用手写输入法来记录一些灵感或者重要信息,可是怎么...
安卓手机重置 系统设置,轻松恢... 手机用久了是不是感觉卡顿得厉害?别急,今天就来教你怎么给安卓手机来个大变身——重置系统设置!想象你的...
win如何安装安卓系统,Win... 哇,你有没有想过,让你的Win系统也能玩转安卓应用?没错,就是那种在手机上轻松自如的安卓系统,现在也...
苹果qq和安卓系统,跨平台体验... 你有没有发现,现在手机市场上,苹果和安卓的较量可是越来越激烈了呢!咱们就来聊聊这个话题,看看苹果QQ...