1回答
我正在尝试验证图(G= V，E)的最小生成树(T = V，ET)。有没有一种方法可以验证它，比如return true，否则它就是一个MST，return False？谢谢
浏览 10提问于2021-06-27得票数 0
3回答
我正在尝试寻找一种有效的方法来检测给定的图G是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有3种不同的最小生成树。我考虑过的最简单的解决方案是运行Kruskal的算法一次，然后找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法，并检查新<
浏览 1提问于2013-05-16得票数 6
我有一个邻接矩阵格式的图，这个图有断开连接的树。我需要找到每个断开的树的MST。所以，我应该先为每棵树找到子图，然后在树上使用MST，还是有更好的方法/算法？
浏览 4提问于2016-05-03得票数 2
回答已采纳
1回答
连接点集的算法？
、、
我们想把它们和任意数量的线连接起来，这样，对于每一对点A，B--有一条从A到B的路径(可能是通过另一个点间接地)--而这些线的总长度最小。+------------------++------+-----------+
对于N= 3，假
浏览 3提问于2013-12-08得票数 2
回答已采纳
1回答
一个具有n个顶点和m个边的加权无向图若对每条边(u，v)的权重小于或等于从u到v的任何其他交替路径的长度，则称为满足三角不等式。证明了对于这样一个图，所有边的总权重是<= ( MST +1)*MST，其中MST是最小生成树的所有边的总权重。
(提示:不属于最小生成树的图的边的最大可能权重是多少？)
浏览 2提问于2015-10-09得票数 1
回答已采纳
1回答
当我看到时，这个问题突然浮现在我的脑海中。为了简单起见，我们可以将讨论限制在无向、加权、连通图上。显然，如果从图中选择任意节点作为源，Dijkstra不能保证生成MST。然而，它是否保证在一个无向、加权、连通图中必须存在一个节点，如果我们选择它作为源并应用Dijkstra的算法，它将为该图生成一个MST？也许你可以给出一个证据或者一个反例。谢谢!
浏览 1提问于2020-12-16得票数 2
回答已采纳
我正在修改一个测试，并遇到了两个问题，与最小生成树在图中，我不确定，并想测试我的答案。
第一个问题是:如果一个图有多个最小生成树，那么Kruskal和Prim的最小生成树算法会生成相同的树吗？我认为它们不一定是因为算法不同而产生的。Kruskal依赖于按权重排序的边，而Prim则不这样做，因此
浏览 3提问于2014-04-29得票数 2
回答已采纳
2回答
我需要找到尽可能小的代价的生成树，这样A点和B点之间的距离就会尽可能低。例如，我有一个图：。最小最小生成树看起来像。但这会使A和B之间的距离= 3。现在我要做的是：
从步骤2的每条路径生成生成<em
浏览 0提问于2018-10-10得票数 1
2回答
我不想找到所有的最小生成树，但是我想知道其中有多少树，下面是我考虑过的方法：
用prim或kruskal算法求出最小生成树，然后求出所有生成树的权值，当最小生成树的权重等于最小生成树的权重时，增加运行计数器我找不到任何方法来求出所有生成
浏览 4提问于2012-12-13得票数 9
回答已采纳
最小生成树(MST)和所有对最短路径(APSP)有什么区别？另外，有没有什么现实世界的问题，使用它们之间的区别是清晰可见的？
浏览 70提问于2020-08-01得票数 1
回答已采纳
Karger，Klein和Tarjan，“寻找最小生成树的随机线性时间算法”，J. ACM，第42卷，1995年，第321-328页。
否则，最佳解是非常接近线性，但不完全线性。精确的界是O(m logβ(m，n))，其中β函数有一个
浏览 2提问于2013-12-20得票数 0
回答已采纳
3回答
我目前正在优化电网规划，而MST没有很好地解决这个问题，因为如果到主电网的连接是一个辐射点，所有的电力都必须流经一条边，并将经过很长的“电气距离”到达每个耗电量点。我正在研究的问题可能是最小化MW*distance或有功功率矩，但这会产生一个非线性问题。
所以我要找的是一个最小的生成树(不是最优的，只是最有效的)，它最小化到树根的最大电气距离(通过图的</
浏览 1提问于2013-06-27得票数 6
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
云直播
对象存储
腾讯会议活动推荐
腾讯云开发者
