1回答
最小生成树的循环不起作用
、、、
作为三个朋友，我们尝试使用r来解决最小生成树的冲突问题。在解决这个问题时，我们读取了.txt格式的文件，其中包含for ex。"1 2 5 2 4 6“等表示从节点1到2，存在权重为5的边和"1 2 2 4”等边，表示边1-2和2-4之间存在冲突关系。,1], edges_read[k,2]) )){ } }然而，R不能给我们一个解决方案，这个for循环<
浏览 18提问于2021-06-08得票数 0
1回答
我们希望找到与s最小距离树(即在s上运行prim/dijkstra获得的最小距离树)不同的最便宜最小生成树的总成本(定义为所有边的权重之和)。
解决这个问题的最好方法是什么？，并对每个到达顶点v(从u到v的路径上最长的边)进行注释。遍历g中的所有边缘g：并找到不存在于r中的e'=(a
浏览 2提问于2015-12-27得票数 1
4回答
通用最小生成树
、、
我正在阅读科门等地的最小生成树，下面是一般的最小生成树。
假设我们有一个连通的无向图G = (V，E)，它有一个加权函数w:E->R，我们希望为G找到一个最小生成树，这里我们用贪婪的方法。这种贪婪策略由以下“泛型”算法捕获，该算法一次生成最小生成树一条边。该算法管理一组边A，保持以下<e
浏览 3提问于2011-11-16得票数 2
回答已采纳
4回答
我正在研究寻找最小生成树(在加权图的情况下)和查找图是否有哈密顿路径(这取决于哈密顿圈的存在)的算法。我把一切都搞砸了。那么哈密顿路径和生成树之间有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有高效的算法来寻找生成树(可能是最小生成树)，但为什么我们就不能有寻找哈密顿回路的算法呢？我们可以一次增加和删除
浏览 1提问于2011-07-23得票数 14
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Prim则不这样做，因此它们可以从不同<e
浏览 3提问于2014-04-29得票数 2
回答已采纳
1回答
设G=(V，E)是一个无向图，其边都有一个唯一的权重。G有一个唯一的MST是真的吗？或者G也可以有多个MST？
浏览 2提问于2021-01-06得票数 1
回答已采纳
1回答
最近，我对Prims/Kruskals算法进行了一些研究，以求图中的最小生成树，我对以下问题感兴趣：
设G是m个边的n个顶点上的无向图，使得每个边都有一个权重w(e)∈{1，2，3}.是否有算法在时间O(n+m)中求G的最小生成树？显然，您只需在图上运行Prims，就可以得到最小生成树，但不能在所需的时间内运行。我在想，我们可以先把每一
浏览 7提问于2016-02-25得票数 0
1回答
最小生成树唯一最小边与非唯一证明
、、、、
因此，我有一个练习，我应该证明或反驳：( 2)与1)相同，但现在所有的边权都是不同的。那么直观地，我理解对于1)由于不是所有的边权都是不同的，那么一个顶点可能有边e的路径，但也有另一个边e_1，这样如果权重(E)=权(e_1)，那么就有一个生成树，它不包含边e，因为这个图是连通的<
浏览 3提问于2015-10-01得票数 2
回答已采纳
2回答
我对Kruskal的算法有一个基本的认识，这就是我发现的：其中不相交的集合是一个数据结构，它实际上很少使用链接列表或森林树方法来导出最小生成树。我想知道的是，不相
浏览 2提问于2017-08-17得票数 1
我正在使用VirtualBox(es)中的迷你管来实现自己的拓扑结构：采用First VirtualBox和迷你作为控制器。/pox.py forwarding.l2_learning#!emptyNet()mininet@mininet-wm:~/mininet/examples$ sudo python mytopology.pyPing是成
浏览 2提问于2018-12-04得票数 2
7回答
如何找到最大生成树？
、、、
与Kruskal的最小生成树算法相反的算法对它有效吗？我的意思是，选择每一步的最大权重(边)？
有没有找到最大生成树的其他想法？
浏览 4提问于2011-02-14得票数 64
回答已采纳
根据，在无向图中找到最小生成树的步骤如下：
(图中已经包含
浏览 6提问于2020-10-07得票数 0
回答已采纳
3回答
假设有一个图G，它的所有边都有对应于不同整数的权重。所以没有两条边具有相同的权重。设E是G的所有边，emax是E中具有最大权重的边。图G的另一个性质是每条边e都属于图G中的某个圈。我必须证明G的最小生成树不包含边emax。
我可以理解为什么这是真的，因为所有的边都是不同的，并且每条边都属于一个循环，所以最小生成树</em
浏览 2提问于2013-11-28得票数 6
回答已采纳
1回答
给定一个正权重的无向循环图，我如何找到最小的一组要删除的边，从而使该图成为非循环图？算法必须在O((E+V)logV)时间内运行。我试图解决这个问题，并考虑使用贾克斯特拉的算法(因为它也在O(E+VlogV)时间内运行，但我不确定如何前进。
浏览 5提问于2021-06-08得票数 1
给出了一个具有红边和蓝边的图G和一个常数K，设计了一个确定性的线性时间算法，它能找到G的生成树(如果不存在这样的生成树，则返回False )。我们迄今所做的工作：找到最小生成树(使用标准线性时间算法)。因此，我们有一个具有最小权重的生成<e
浏览 1提问于2014-02-11得票数 4
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
