1回答
图中求最小生成树(MST)？
、、、、
给出了一个边上有权的无向图G和2 different最小生成树: T，T‘对于T‘中没有T’的每一个边e，T‘中有一个边e'，它不在T中，所以如果在T中用e'代替e (我们称之为T_new)，那么它仍然是G的最小生成树。我认为我离找到正确的算法太近了，但我坚持了一点：由于T是一棵树，删除e将导致两个分离的组件，
浏览 9提问于2021-05-09得票数 1
2回答
基于DFS的MST算法
、、、
我有以下算法:对于边上具有正权函数的给定(有限无向简单)图G=(V，E)：
运行DFS (深度优先搜索)，直到您发现边缘向后或DFS停止。如果停止，返回G。现在我需要了解这个算法在做什么。我已经证明了算法给了我一个G的生成树，我相信它是一个最小生成树，但是我没有证明。请帮我证明一下。
浏览 4提问于2011-12-09得票数 0
回答已采纳
起源问题来自于的练习，算法的引入。问题是:我认为G 的所有最小生成树不包括 e 的命题是正确的。e 是某些周期上唯一的最大权边.是吗？
浏览 1提问于2016-10-28得票数 1
回答已采纳
1回答
最小生成树唯一最小边与非唯一证明
、、、、
因此，我有一个练习，我应该证明或反驳：( 2)与1)相同，但现在所有的边权都是不同的。那么直观地，我理解对于1)由于不是所有的边权都是不同的，那么一个顶点可能有边e的路径，但也有另一个边e_1，这样如果权重(E)=权(e_1)，那么就有一个生成树，它不包含边e，因为这个图是连通的。否则，如果e_1和e都位于最小生成树中，则存
浏览 3提问于2015-10-01得票数 2
回答已采纳
2回答
最小生成树和最短路径
、、、
我遇到了这样一个问题：
给定一个具有整数权重(正负)的连通有向图，开发一个算法来寻找两个顶点之间的最短路径。我想我可以使用最小生成树算法，例如kruskal的算法，然后使用可能的dijkstra算法来证明，因为在MST中，每个顶点只有一条进入边，dijkstra的算法甚至可以在负权重下工作。附注：我很难证明MST包含每个顶点的有向图的最短路径。
浏览 1提问于2012-11-08得票数 0
3回答
我必须证明G的最小生成树不包含边emax。
我可以理解为什么这是真的，因为所有的边都是不同的，并且每条边都属于一个循环，所以最小生成树算法可以简单地选择包含emax的循环中权重较低的边。但我不确定如何具体证明这一点。
浏览 2提问于2013-11-28得票数 6
回答已采纳
2回答
这是一种在连通的无向图G=(V，E)中求最小生成树的算法：
在图(S，V\S)中选择一些不属于横过它的(s，u) 不是是“交叉”边我可以在证据中使用以下几点：
在算法的任何一点上，都存在一个最小生成树T=(V，Et)，它包含算
浏览 2提问于2018-03-30得票数 0
回答已采纳
2回答
，我需要用Prim的和Kruskal的算法找到G的最小生成树。我很难用Kruskal算法找到最小生成树。我看过很多与Kruskal的图形算法相关的视频，但我最终得到了与Prim算法相同的图形。
有人能告诉我如何用Kruskal算法求图的最小生成树
浏览 1提问于2019-03-17得票数 0
回答已采纳
2回答
我正在尝试编写一个算法，来判断是否存在恰好有k条黑边的生成树(不一定要找到真正的树)。但我很难去思考，在这个范围内，是否每个k都必须有一棵生成树。我的直觉是肯定的，它对我尝试过的每个例子都有效，但我不知道如何证明这一点。
浏览 0提问于2010-12-06得票数 3
考虑到Prim的算法，顶点的最小边缘要么已经在树中，要么最终会被选择。如果这句话是假的，谁能给我举个反例？
谢谢。
浏览 3提问于2022-03-25得票数 0
回答已采纳
2回答
我目前正在研究图及其算法，我注意到一个我不知道能确切证明的问题：
如果我们有一个连通的无向图G=(V，E)和每个边都有weight=1，那么每一棵从根建立的最短路径的生成树都是最小生成树吗？我用做了一些例子，我觉得这个问题的答案是正确的，但是有人可以告诉我如何证明这一点？另一个在我脑海中闪现的问题，是不是另一个方向也是正确的？
浏览 1提问于2015-12-21得票数 3
回答已采纳
1回答
反向删除算法:从包含所有边的图开始。然后按权重的递减顺序重复通过边缘。对于每条边，检查删除该边是否会断开该图的连接；如果不会，则删除它。
如何证明此算法计算MST？
浏览 3提问于2020-03-27得票数 0
2回答
我希望我的最小生成树算法基准与最好的。有人知道在哪里可以找到这些算法的C++实现吗？我大摇大摆地搜索了一下，却什么也没找到。如果这些算法是最好的，那么肯定有一个C++实现吗？--迄今最快的最小生成树算法是由David、Philip和Robert提出的，他发现了一种线性时间随机算法，它是Borůvka算法和反向删除算法的结合。函数α增长非常慢，因此在实际应用中，它可
浏览 2提问于2011-02-07得票数 11
回答已采纳
注:C‘为logc，基数为17用线性函数对每条边的代价进行变换，很容易证明结论是正确的。
我没有考虑具体的算法，比如贪婪的算法。我只考虑了变换后两棵树的权重之和之间的关系。如果G生成的一棵树有两个边a和b，由G生成的另一棵树有c和d，a+b<c+d，第一棵树是MST，但在变换图G‘中，第二
浏览 8提问于2020-08-12得票数 2
回答已采纳
我试图设计一个算法，其中给定一个连通加权图G= (V，E)和V中的一个顶点子集U将构造一个最小生成树，使得U中的所有顶点都是叶(其他顶点也可能是叶)，或者返回不存在这样的树(False)。这就是我所得到的全部，采用Prim的算法(公平警告，它非常糟糕；甚至不知道它是否有效/是否有效，或者使用什么数据结构，我会接受其他任何正确的算法)： r
浏览 3提问于2020-10-15得票数 2
回答已采纳
2回答
如果我们修改最短路径问题，使得两个顶点之间的路径的成本是其上边的成本的最大值，那么对于任何一对顶点u和v，它们之间遵循最小成本生成树的路径是最小成本路径。
我如何证明这种方法是正确的？有没有人知道文献中是否存在这种算法？它有名字吗？
浏览 0提问于2011-11-02得票数 3
回答已采纳
4回答
最小生成树子图
、、、、
目前我的想法使我相信，既然我们已经有了最小生成树G，那么既然我们在最小生成树中有子节点，就必须存在G‘。就目前情况而言，我有点不知所措。设(V，T)是G的最小生成树，G‘=(V’，E‘)是G的连通子图。(b)在什么条件下(V‘，E’∩T)是G‘的最小生成树</e
浏览 2提问于2012-10-29得票数 4
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
即时通信 IM
腾讯会议活动推荐
腾讯云开发者
