1回答
假设我们有一个无向加权(在边上)图G(V，E)，需要将每个e∈G(V，E)分成以下类型： Type1:每个MST中都包含egdge e。 Type2:边e至少包含在一个MST中，但不是全部。Type3:边e不属于MST。 为了做到这一点，我考虑使用Kruskal的算法，但稍作修改。如果find()函数没有检测到循环，我将正在处理的边命名为Type1。如果find()找到一个循环，我运行第二个find()来查看在这个循环中是否有与值为p
浏览 13提问于2019-01-11得票数 0
回答已采纳
1回答
带度约束的最小生成树
、、、、
我必须解决这个问题：
对于每个得到的连接组件C1，…，Cm使用例如Kruskal或Prim的算法找到MST。重新添加顶点u，并为每个词添加1和C
浏览 10提问于2015-05-17得票数 2
回答已采纳
这就是问题，我承认这是一个家庭作业问题，我不是在寻找答案，而是我只想知道我是否在朝着正确的方向前进，如果我没有正确的方向，请告诉我正确的方向。问:证明了如果加权图中没有两条边具有相同的权重，则每个最小生成树(MST)中都包含与顶点v关联的权重最小的边。我的回答是:给定一个顶点( V )和一个加权图(G)，我们注意到∃(存在)和与V相关的<
浏览 0提问于2011-11-28得票数 0
回答已采纳
3回答
我正在尝试寻找一种有效的方法来检测给定的图G是否有两个不同的最小生成树。我还试图找到一种方法来检查它是否有3种不同的最小生成树。我考虑过的最简单的解决方案是运行Kruskal的算法一次，然后找到最小生成树的总权重。然后，从图中删除一条边，再次运行Kruskal算法，并检查新树的权重是否为原始最小生成树的权重，对图中的每条边也是如
浏览 1提问于2013-05-16得票数 6
2回答
我有一个加权图，我想为这个图计算一个新的加权函数，这样边权是不同的，新图中的每个MST都对应于旧图中的MST。新的图将只有一个MST，因为所有的边都是不同的。
浏览 5提问于2017-10-26得票数 2
回答已采纳
我们知道原始的图和原始的MST。现在我们改变图中的k个边权重。有没有办法在O((n + k) log )时间内从旧图生成新的MST？
浏览 0提问于2014-10-21得票数 1
最小生成树(MST)和所有对最短路径(APSP)有什么区别？另外，有没有什么现实世界的问题，使用它们之间的区别是清晰可见的？
浏览 70提问于2020-08-01得票数 1
回答已采纳
1回答
在无向连通图中，如果e是与顶点v相邻的最轻边，那么e是某个MST的一部分吗？
我说是，因为MST选择了所有最亮的边缘，这是正确的想法吗？
浏览 0提问于2018-05-04得票数 1
2回答
我试图从加权无向图中求出第二次最佳最小跨越3。我知道如何使用Kruskal算法计算MST，我正在考虑这样找到第二最佳最小算法：
这应该是第二好的MST</e
浏览 4提问于2017-04-18得票数 0
回答已采纳
我的家庭作业有以下问题：
(这项任务允许我们从其他人那里得到帮助，所以这不是作弊。)我想我可以做一个BFS，找出这个边是否是两个层之间的边，如果是这样的话，这个边是否是这些层中最小的边。但是，当这个边不是BFS树的树边时，我能说什么呢？
浏览 2提问于2011-09-02得票数 11
回答已采纳
1回答
如果不属于MST的图中的边的权重减少了，我试图修改最小生成树。我在堆栈溢出上看到，首先将边缘连接到MST，现在MST中正好有一个循环，而在循环特性中，可以从MST中删除权重最大的边？如何在那个周期中找到最大重量边？
浏览 1提问于2015-01-02得票数 2
回答已采纳
1回答
一个具有n个顶点和m个边的加权无向图若对每条边(u，v)的权重小于或等于从u到v的任何其他交替路径的长度，则称为满足三角不等式。证明了对于这样一个图，所有边的总权重是<= ( MST +1)*MST，其中MST是最小生成树的所有边的总权重。
(提示:不属于最小生成树的图的边的最大可能权重是多少？)
浏览 2提问于2015-10-09得票数 1
回答已采纳
既然最短路径已经是“最短的”，那么它有可能比MST中的任何其他路径都长吗？我知道这两个顶点之间的路径通常比两个顶点之间的最短路径长，但它能更短吗？
浏览 18提问于2020-02-05得票数 1
2回答
基于特定条件创建图形
、、、
我有一个问题，要求我制作一个图，使图中的BFS和DFS树不是最小生成树，并且邻接表的顺序并不重要。我知道BFS DFS和MST的属性，但我对这个问题感到困惑。我应该如何处理这个问题？
浏览 0提问于2017-11-14得票数 2
2回答
我得到了一张上面有成本和字母的图表。我的任务不是寻找从一个节点到另一个节点的最佳路径，而是寻找最小生成树。 为此，我做了一些表格，并标记了这棵树的最佳路径。 ? ? 尽管如此，目的不是找到从A到K的最佳路径，而是MST。
浏览 58提问于2019-02-05得票数 2
是否可以通过简单地遍历图中的顶点并从该顶点中选择最小的边并取所有这些边的并来创建MST？这似乎与削减属性并不矛盾，而且比实现Prim的算法更有效。
浏览 3提问于2020-03-14得票数 0
回答已采纳
1回答
我试图得到一个无向加权graph.However的最小生成树，我需要找到一个或多个nodes.After之间的最短路径，这就是，我必须找到一个图的最小生成树。我已经找到了必要节点之间的最短路径，但是我不知道如何找到最小生成树，包括这些最短路径。让我举一个例子。A F ------B E -----D-----C在A和E之间还有一个有2磅重的边缘现在，首先我需要找到A和E之间的</
浏览 2提问于2013-12-22得票数 1
云服务器
ICP备案
腾讯会议
云直播
对象存储
腾讯云开发者
