展开

关键词

成树(Kruskal和Prim

而今天我们要说一个非常实用的——成树的建立!这是图论中一个经典问题,可以使用Kruskal和Prim两种来进行实现! 在实际中,这种的应用非常广泛,比如我们需要在n个城市铺设电缆,则需要n-1条通信线路,那么我们如何铺设可以使得电缆短呢?成树就是为了解决这个问题而诞的! ? 成树 如上图所示,一幅两两相连的图中,找到一个子图,连接到所有的节点,并且连接边的权重小(也就是说边的数量也是小的,这也保证了其是树结构). 2 Kruskal(克鲁斯卡) Kruskal 是一种贪心,我们将图中的每个edge按照权重大小进行排序,每次从边集中取出权重小且两个顶点都不在同一个集合的边加入成树中! 4 资源分享 以上完整代码文件(C++版),文件名为:成树(Kruskal和Prim).cpp,请关注我的个人公众号 (工程师之路),回复"左神基础CPP"即可获得,并实时更

2.4K30

成树-Prim和Kruskal

Prim 1.概览 普里姆(Prim),图论中的一种,可在加权连通图里搜索成树。 下面对的图例描述 image.png 3.简单证明prim 反证:假设prim成的不是成树 1).设prim成的树为G0 2).假设存在Gmin使得cost(Gmin)<cost(G0 1.概览 Kruskal是一种用来寻找成树的,由Joseph Kruskal在1956年发表。 阶图G'(u,v的合并是k+1少一条边),G'成树T'可以用Kruskal得到。 于是假设不成立,T'+{<u,v>}是G的成树,Kruskal对k+1阶图也适用。 由数学归纳,Kruskal得证。

2.1K100
  • 广告
    关闭

    腾讯云618采购季来袭!

    一键领取预热专享618元代金券,2核2G云服务器爆品秒杀低至18元!云产品首单低0.8折起,企业用户购买域名1元起…

  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    |Prim成树

    02 — 成树 看下成树的定义 在一给定的无向图 G = (V, E) 中,(u, v) 代表连接顶点 u 与顶点 v 的边,而 w(u, v) 代表此边的权重,若存在 T 为 E 的子集且为无循环图 ,使得 w(T) 小,则此 T 为 G 的成树。 成树可以用kruskal(克鲁斯卡尔)或 prim(普里姆)求出。 03 — prim(普里姆) 描述 输入:一个加权连通图,其中顶点集合为V,边集合为E; 初始化:Vnew = {A},其中 A 为顶点集合V中的任一节点(起始点),Enew = {},为空; 得到的成树如下: D / \ A F \ B / E / \ G C 总费用小为39 05

    2.7K70

    Kruskal-成树

    思想: 1 将G的n个顶点看成n个孤立的连通分支,所有的边按权从小到大排序 2 当查看到第k条边时,   如果断点v和w分别是当前的两个不同的连通分支t1和t2中的顶点时,就用边(v,m)j将t1,

    75350

    Prim-成树

    基本思想: 1 置S={1} 2 只要S是V的真子集就做如下的贪心选择:   选取满足条件的i ,i属于S,j输入V-S,且c[i][j]小的边,并将定点j加入S中   这个过程直到S==V为止。 3 这个过程所选的边,恰好就是成树 描述: void Prim(int n,Type * * c) { T = 空集; S = {1}; while(S ! = V) { (i,j)=i 属于 S 且 j属于V-S的小权边; T = T∪{(i,j)}; S = S ∪ {j}; } } 模版代码

    1.3K60

    成树(Prim和Kruskal详解)

    前言 在数据结构与的图论中,(成)成树是一种常用并且和活贴切比较近的一种。但是可能很多人对概念不是很清楚。 成树可以用kruskal(克鲁斯卡尔)或prim(普里姆)求出。 通俗易懂的讲就是成树包含原图的所有节点而只用少的边和小的权值距离。 通过这个图我们使用某种形成成树的就可以叫做成树。具体实现上有两种实现方、策略分别为kruskal和prim。 在这里插入图片描述 Prim 除了Kruskal以外,普里姆(Prim)也是常用的成树。虽然在效率上差不多。但是贪心的方式和Kruskal完全不同。 prim的核心信仰是:从已知扩散寻找小。它的实现方式和Dijkstra相似但稍微有所区别,Dijkstra是求单源短路径。而每计一个点需要对这个点从距离。

    2.5K20

    成树之Prim和Kruskal

    一个连通图可能有多棵成树,而成树是一副连通加权无向图中一颗权值小的成树,它可以根据Prim和Kruskal得出,这两个分别从点和边的角度来解决。 Prim 输入:一个加权连通图,其中顶点集合为V,边集合为E; 初始化:Vn = {x},其中x为集合V中的任一节点(起始点),Enew = {}; 重复下列操作,直到Vn = V:(在集合 E中选取权值小的边(u, v),其中u为集合Vn中的元素,而v则是V中没有加入Vn的顶点(如果存在有多条满足前述条件即具有相同权值的边,则可任意选取其中之一); 将v加入集合Vn中,将(u, v)加入集合 En中;) 输出:使用集合Vn和En来描述所得到的成树。

    99720

    成树----prim----普利姆

    成树的概念 ? ? 成树的定义 ? 成树的代价和成树 ? MST性质 ? ? 普利姆(prim) ? 图解: ? ? ? ? ? ? ? ? ? 使用哪一种结构进行存储? int j = 0; j < verNum; j++) { cout << arc[i][j] << " \t"; } cout << endl; } } //prim shortEdge* se,int k) { cout << "(" << se[k].adjvex << "," << k << ")" << se[k].lowcost << endl; } //Prim ,如果加入的顶点K到他的邻接点的代价小于当前lowcost数组中记录的代价,就进行替换 for (int i = 0; i < verNum; i++) { //当前K顶点在边数组里面与每个顶点之间的权值与结构体数组 复杂度 ?

    67130

    仿qq侧滑菜单

    github地址 https://github.com/sunguowei 近项目要做一个QQ5.0的侧滑菜单效果,和传统的侧滑菜单存在着一些差异。想必大家都已经见识过了。 后的效果如下。当然了,还有很多可以优化的地方,后续再慢慢优化。 ? 备注:如果图片动画显示不出来,可以点击这个网址查看。 https://github.com/jfeinstein10/SlidingMenu 备注:SlidingMenu使用了SherlockActionBar这个库,配置起来会比较麻烦,在文章的后我会把 super(context, attrs, defStyle);   /** SlidingMenu是一个RelativeLayout,这里把背景图ImageView添加到RelativeLayout的底层 后,附上Demo的下载地址。

    89790

    Fluxion仿TPLINK界面

    仿TPLINK钓鱼界面版 Fluxion仿TPlink钓鱼界面 优化了logo 修复了版权问题 美化的正确页面和失败页面 优化了加载速度 image.png 下载地址 仿TPINK钓鱼界面 更到2.0 支持管理员密码 更日志: 废弃了部分css 修复了头部样式 增加了路由器管理员密码 效果 image.png 使用方 请参考文件附件,管理员密码会保存到 /root/admin.txt 中! 仿TPINK钓鱼界面管理员版 仿TPlink调用界面(管理员版)3.0发布 更日志: 增ssidMAC 信息 优化了图片显示 修复了标题问题和favicon 图标 效果 image.png 下载 仿

    25520

    成树(上)——Prim(普里姆)

    对于成树著名的有两种:Prim与Kruskal。 ---- Prim Prim思想描述: Prim可以简单描述成一句话:让一个小树慢慢长大。 即从输入的起始结点看成一棵树,之后一步步收录那些与已经被收录结点相邻近的结点。可以看出Prim堆稠密图较为合适。 Prim过程描述: 1)首先定一个成树MST初始化为空(即不含有任何边),初始化距离数组dist为正无穷,表示所有结点到成树的距离(即不可达),定义父亲数组parent来记录一个结点的父亲结点 //普里姆(Prim),已vertex为根节点的的成树 int Prim(int vertex){ int cnt = 0; / = -1){ cout<<"Prim成的成树的权重和为:"<<endl; cout<<min_weight<<endl; graph.Print_Prim

    43820

    Java实现成树之Kruskal

    近做大题目主要运用的都是数据结构方面的题,既有之前的短路径的相关的,也有现在的成树,这里先讲解Kruskal,主要是我先在刚会这个,prim,明天再看。 Kruskal其实和之前的djs有点类似,主要还是每次循环找出局部优解,也就是小权重的那条路,一次寻找即可,这里作者一开始俊德实现起来并不麻烦,但之后发现,循环找出优解不是麻烦的,大不了每次排序 ,就行了,但是之后发现难的一块是不能出现环,举个例子, ? 接下来就是简单的成树以及并查集的代码了: import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; } } static class node implements Comparable<node>//创建一个内部类并且实现Comparable接口,这样当使用Arrays.sort方是就能直接排序了

    64240

    图的成树

    Ok,那么成树是什么呢? 求成树的主要有两种:克鲁斯卡尔(Kruskal)和普里姆(Prim)。 下面我们来看一下 Prim 的核心思想: 我们换个角度思考一下:既然后我们需要的成树一定要有 n 个顶点,那么我们直接向这个成树加入图的顶点就行了。 Prim不需要用到查并集的思想,它使用的是 Dijkstra 单源短路径的思想,只不过我们这里把源节点换成了成树,如果你熟悉 Dijkstra ,那么我觉得 Prim 对你一点难度都没有 count++; /* * 更成树的总权值:成树的总权值等于成树原来的权值 * 加上刚刚加入成树的顶点到成树的距离

    1.6K20

    成树的Kruskal

    定义: 一个有 n 个结点的连通图的成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的少的边。 [1] 成树可以用kruskal(克鲁斯卡尔)或prim(普里姆)求出。 Kruskal简述: 假设 WN=(V,{E}) 是一个含有 n 个顶点的连通网,则按照克鲁斯卡尔构造成树的过程为:先构造一个只含 n 个顶点,而边集为空的子图,若将该子图中各个顶点看成是各棵树上的根结点 item1, item2): self[item2] = self[item1] def Kruskal_1(nodes, edges): '''基于不相交集实现Kruskal forest.unionset(parent1, parent2) pass def Kruskal(nodes, edges): ''' Kruskal 无向图成树

    73620

    成树实现与分析:Prim ,Kruskal

    非强连通图的极大连通子图叫做强连通分量; 成树:一个有n个节点的连通图的成树是原图的极小连通子图,且包含了原图中的所有n个节点,并且有保持图连通的少的边;成树可以使用Kruskal和 Prim:此可以称为加点,使用贪心思想进行求解,Vnew Vold-new 之间,代价小的边对应的点,加入到Vnew之中;从任意一节点开始,知道Vnew中包含所有的点; 图中所有顶点集合 加入到Vnew之中; 重复上述步骤,直到Vnew包含所有的点; 证明:假设权值小的边不在成树中,此时将权值小的边加入成树中,必然会构成一个回路,去掉回路中权值大的边,构成一个成树 Kruskal:此可称为加边;初始成树边数为0,每次就选择一条满足条件的小代价的边,加入到成树的边集合中; 把图中的所有边按代价从小到大排序; 把图中的n个顶点,看成独立的n棵树组成的森林 实现参考:https://github.com/yaowenxu/codes/tree/master/成树 保持更,转载请注明出处;更多内容请关注cnblogs.com/xuyaowen

    47620

    成树的两种方(Kruskal和Prim

    成树:在连通网的所有成树中,所有边的代价和小的成树,称为成树。 ? 下面介绍两种求成树 1.Kruskal可以称为“加边”,初始成树边数为0,每迭代一次就选择一条满足条件的小代价边,加入到成树的边集合里。 Prim可以称为“加点”,每次迭代选择代价小的边对应的点,加入到成树中。从某一个顶点s开始,逐渐长大覆盖整个连通网的所有顶点。 由于不断向集合u中加点,所以小代价边必须同步更;需要建立一个辅助数组closedge,用来维护集合v中每个顶点与集合u中小代价边信息,: struct { char vertexData .lowestcost = 0; //代价置为0 for (int i = 0; i < vexCounts;i++) //更v中顶点小代价边信息 {

    85630

    Kruscal(成树)模版

    1 const int maxn=400;//大点数 2 const int maxm=10000;//大边数 3 int n,m;//n表示点数,m表示边数 4 struct edge{int

    51640

    小依赖图重

    省略其他依赖关系梳理 可以看到在angualrjs中我们没有办直接表达依赖关系,只能通过$watch来在某个值发变化时,做一个计,从而使另外一个值发变化。 在这种等级划分中,我们确定哪些变量先重,哪些后重,也就是分批计。而这个分批次的,就是本文的重点。先按住不讲。通过这个分批之后,每个变量我只需要计一次。 你可以这样思考,比如我们拿c举例,如果a发变化的时候,马上去重c,紧接着,b也会由于a变而发变化,c还需要再计一次才能得到正确结果。 基于这个,我们实际上不需要去提炼小依赖图,而可以直接用全图,因为即使我上全图,但是后的计量也只局限于需要重的那些变量而已。 这样,我们就省去了从全图找出小依赖图的这个过程,省了一些性能。 好了,接下来是揭秘怎么实现分批的。 我们还是用图来说话吧。

    13020

    :图解成树之普里姆(Prim)

    找连通图的成树,经典的有两种,普里姆和克鲁斯卡尔,这里介绍普里姆。 为了能够讲明白这个,我们先构造网图的邻接矩阵,如图7-6-3的右图所示。 ? 下面我们对着程序和每一步循环的图示来看: 代码:(改编自《大话数据结构》) /* Prim成树  */ void MiniSpanTree_Prim(MGraph MG) {      即成树的边为:(0, 1), (0, 5), (1, 8), (8, 2), (1, 6), (6, 7), (7, 4), (7, 3) 后再来总结一下普里姆的定义: Screenshot (17).png 由代码中的循环嵌套可得知此的时间复杂度为O(n^2)。 对比普里姆和克鲁斯卡尔,克鲁斯卡尔主要针对边来展开,边数少时效率比较高,所以对于稀疏图有较大的优势;而普里姆对于稠密图,即边数非常多的情况下更好一些。

    1.4K90

    成树(下)——Kruskal(克鲁斯卡尔)

    概要 在我的上一篇文章成树(上)——Prim(普里姆) 主要讲解对于稠密图较为合适的Prim。那么在接下里这片文章中我主要讲解对于稀疏图较为合适的Kruskal。 ---- Kruskal Kruskal思想概述: 如果说Prim可以用让一颗小树慢慢长大,那么Kruskal也可以用一句话来总结:将森林合并成树。 就是说它比Prim更直接的贪心,把每个顶点看成一棵树,那么恶整个图就是一个森林。要做的就是一步一步的把小的边收录到成树且与成树里的边不构成回路。 Kruskal过程: 1)首先构造一个有所有顶点构成的并查集(利用路径压缩),并构成的边小堆。 = -1){ cout<<"Kruskal成的成树的权重和为:"<<endl; cout<<min_weight<<endl; graph.Print_Kruskal

    64920

    相关产品

    • 智慧党建

      智慧党建

      智慧党建是互联网与基础党建工作的有效融合,运用信息化新技术,以数字化、网络化、智能化提高服务群众水平。智慧党建支持常用党建场景,采用“分层分级”的管理理念,聚集党建最新信息,通过小程序登录即可使用……

    相关资讯

    热门标签

    扫码关注云+社区

    领取腾讯云代金券