博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
最小生成树模板 加 例题分析 (最小生成树类型汇总)
阅读量:5858 次
发布时间:2019-06-19

本文共 1993 字,大约阅读时间需要 6 分钟。

最小生成树:对于一个无向连通图的最小生成树,选取边使得图中每个顶点连通且花费最小。

在kruskal算法中,集合A是一个森林,加入集合A中的安全边总是图中连接两个不同连通分支的最小权边。prim算法中,集合A仅形成单颗树,添加入集合A的安全边总是连接树与一个不在树中的顶点的最小权边。

kruskal在图G(v,e)上的运行时间取决于不相交集合数据结构是如何实现的,模板中采用路径优化的并查集,时间复杂度为O(1)。然后对时间复杂度有影响的就是对边的排序,其最终时间复杂度O(E lgV);

prim算法适用于边多的,反之为kruskal算法。鉴于kruskal代码的简单易操作,例题解法均为kruskal算法。

Kruskal伪代码

(1)对所有的边从小到大排序

(2)while(n>1) do{

                取权值最小的边(u,v);

                if(u,v不连通){

                        将(u,v)加入T;

                        n--;

                }

                将边(u,v)从集合E中删除;

         }

其中判断两点是否连通可使用并查集 

模板: 

例题及扩展:(全部做完就可以成为入门菜鸟了)

基础例题:

常用套路:n个结点的最小生成树由n-1条边构成,基础题一般会提前连接好一些点,将这些点加入并查集并计算还需加入多少边即可

难度:easy

题意:构建最小生成树,会给出一些已经连接好的点。 

解析:将给出的已连接点提前加入并查集,计算还需加入多少条边才能构成最小生成树,然后加边即可。

代码:

 

难度:easy

题意:构建最小生成树,使得生成树的最长边减去最短边所得的值最小。

解析:对于所有的边从小到大排序,每次枚举一个区间【L,R】,区间长度为n-1,比较每次的结果求最小值

代码:

 

难度:medium

题意:给一张图和多个子网,子网已经连通且花费固定,求把图连通的最小花费)

解析:运用子集生成枚举子网,每次将子网中的点提前加入并查集,计算还需加入多少条边才能构成最小生成树,再构建               生成树,比较每一次的结果取最小值

代码:

 

 

继续学习一些概念:

(1)切割性质。假设所有边权均不相同。设S为非空也非全集的V的子集,边e是一个端点在S中,一个不在的边中权值最小的,则图所有的生成树都包含e

(2)回路性质。假设所有边权均不相同。设C为图中的任意回路,边e是C上权值最大的边,则图所有的生成树不包含e。

增量最小生成树:从包含n个点的空图开始,依次加入m条带权边。每加入一条边输出当前图的最小生成树的权值(不连通输出无解)每次求解完整的最小生成树的时间复杂度为O(m^2logn),显然不行。

可行节点数到达n-1时刚好构成一个最小生成树,后面继续加边则根据回路性质,加入边e(u,v)时,找到u到v的唯一路径上权值最大的边,与e进行比较,删除权值较大的边把其他所有边删除。

最小瓶颈生成树:给出带权无向图,求一颗生成树,使其最大边权尽可能小。(就是最小生成树)

最小瓶颈路:给出带权无向图,求u到v的一条路径,使得路径上的最长边尽量短。求最小生成树,起点终点都在树上的唯一路径就是要找的路径(uva10048)

最小瓶颈路最大边长:求出最小生成树,用dfs将其转化为有根树,计算maxcost【u】【v】,从v出发访问一个新节点u时,考虑所有已经访问过的结点x maxcost【x】【u】=max(maxcost【x】【v】,maxcost【v】【u】),复杂度为O(n^2)

次小生成树:如果最小生成树不唯一,则次小生成树的权值与最小生成树相同。

枚举要加入哪一条新边,最小生成树加入边u-v后,图中会出现一条回路,所以要删除的边在最小生成树u到v的路径上,而且是这条路径的最长边。即次小生成树一点可以由最小生成树加一条边,删去一条边得到。

所以只需要按照“每对结点间的最小瓶颈路”求出每对结点在最小生成树唯一路径上的最长边maxcost【u】【v】

 

生成树变种类型的问题:

难度:medium easy

题意:给出网络和某些特定的点,删除网络上的边使得这些特定点之间两两互不不连通,且花费最小。

解析:构建最大生成树(边按从大到小排序后执行kruskal算法),当一条边的两端点都是给定的点时,花费加上这条边,             反之加入最大生成树。最后得到的是多个包含一个给定点的最大生成树(一个端点也可以看做),最大生成树之间               不相连,自己思考一下为什么达到了题目的条件)

代码:

 

难度:medium

题意:城市有人口总数,城市之间有道路,将城市连接起来的花费为B。你可以免费连接两个城市,免费连接的两个城市人             口之和为A。找一个使得A/B最大的方案

解析:先求出最小生成树,枚举u,v并删除最小生成树中u,v连接路径上边长最长的边,比较没种情况的结果

代码:

转载于:https://www.cnblogs.com/zhizhaozhuo/p/9594209.html

你可能感兴趣的文章
脚本输出EBMIDE——断点跟踪输出
查看>>
(转)最近一个项目中关于NGUI部分的总结(深度和drawCall)
查看>>
数据字典生成工具之旅(8):SQL查询表的约束默认值等信息
查看>>
ruby环境sass编译中文出现Syntax error: Invalid GBK character错误解决方法
查看>>
Kali linux渗透测试常用工具汇总2-渗透攻击
查看>>
[转]C#三层架构登陆实例
查看>>
java String->float,float->int
查看>>
更改EBSserver域名/IP
查看>>
ubuntu14.04 64位JDK安装
查看>>
我是这样手写Spring的,麻雀虽小五脏俱全
查看>>
都说产品经理要“会说话”?
查看>>
从0到1使用Kubernetes系列(三)——使用Ansible安装Kubernetes集群
查看>>
一本走心的 JS-Native 交互电子书
查看>>
(三)神经网络入门之隐藏层设计
查看>>
解读“重定向SMB”攻击
查看>>
Ruby实例方法约束简谈
查看>>
Xcode9更新之后项目遇到的问题
查看>>
基于RxJava2实现的简单图片爬虫
查看>>
RxJava2 实战知识梳理(6) 基于错误类型的重试请求
查看>>
谈谈 Web 安全
查看>>