问题标签 [minimum-spanning-tree]

Dijkstra通常用于查找图中两个节点之间的最短距离。它可以用来找到最小生成树吗？如果是这样，怎么做？

编辑：这不是家庭作业，但我试图理解一个旧练习考试的问题。

我一直在学习 Cormen 等人的书，我对他们提供的算法有点困惑。我已经通过维基百科了解 Prim 算法的概念是如何工作的，但我无法使用我书中提供的算法来模仿这种工作方式。

请参阅本章的在线副本： http ://www.cs.cmu.edu/afs/cs/academic/class/15451-s04/www/Lectures/minimumSpanningTrees.pdf

算法在上述链接的第 13 页给出，示例图在前一页。

现在，在示例案例中使用算法，在第一步中：

u <--- 节点 A 到 ExtractMin(Q)。然后根据图表在 Adj[u] 中有两个条目：节点 b 和节点 h。

现在首先设置 v <---- 节点 b。然后检查 v 是否属于 Q。确实如此。检查是否 w(u,v) < key[v]。真的。所以 PI[v] <--- u 和 key[v] <--- w(u, v)。我得到了这么多。这显示在第 12 页图表的 (b) 中。

但是算法说“对于 Adj[u] 中的每个 v”。

所以下一步应该设置v <---节点h。然后检查 v 是否属于 Q。确实如此！w(u,v) < key[v]？这是！因为 key[v] = 无穷大！但是该图显示了 (c) 部分的不同步骤！

啊啊啊！为什么？

如果我们有一个（任意）连通无向图 G，其边具有不同的权重，

1. G 的每个 MST 是否都包含最小加权边缘？
2. 是否存在不包含最大加权边缘的 G 的 MST？

此外，如果有人能提示在处理此类 MST 问题时必须牢记的关键事项，我将更加感激。

这是一个家庭作业问题。谢谢。

我在大学遇到了以下问题：

令G = (V, E)是一个（无向）图，在边e ∈ E上具有成本c _e >= 0 。假设给定G中的最小成本生成树T。现在假设一条新边被添加到G中，连接两个节点v，t _v ∈ V，成本为c。

1. 给出一个有效的算法来测试T是否仍然是最小成本生成树，并将新边添加到G（但不添加到树T）。让你的算法在 O(|E|) 时间内运行。你能在 O(|V|) 时间内完成吗？请注意您对用于表示树T和图G的数据结构所做的任何假设。
2. 假设T不再是最小成本生成树。给出一个线性时间算法（时间 O(|E|)）将树 T 更新为新的最小成本生成树。

这是我找到的解决方案：

它似乎有效，但我可以轻松地在 O(|V|) 时间内运行，而问题需要 O(|E|) 时间。我错过了什么吗？

顺便说一句，我们有权向任何人寻求帮助，所以我没有作弊 :D

给定具有加权边的有向图，可以使用什么算法来给出具有最小权重的子图，但允许从图中的任何顶点移动到任何其他顶点（假设任何两个顶点之间的路径始终存在） .

这样的算法存在吗？

我一直在寻找一种实现（我正在使用networkx库。）它将找到无向加权图的所有最小生成树（MST）。

我只能找到 Kruskal 算法和 Prim 算法的实现，这两种算法都只会返回一个 MST。

我看过解决这个问题的论文（例如Representing all minimum spanning trees with applications to count and generation），但我的脑袋往往会因为试图思考如何将其转换为代码而爆炸。

事实上，我无法找到任何语言的实现！

我的老师要求我们为这个问题实施一个动态编程解决方案，但我认为一个不存在，因为我无法使用谷歌找到它。

无论如何，给定一个图表和 ak，比如 3，你必须从中找到 3 个最好的 MST。如果该图没有 k 个子树，则可以多次返回同一棵树或次优树。

我实在想不出解决办法。

我一直在阅读有关最小生成树的切割属性的在线演示文稿和教科书。我真的不明白它应该说明什么，甚至为什么它是实用的。据说它有助于确定要添加到 MST 的边缘，但我看不到它是如何实现的。到目前为止，我对 cut 属性的理解是将 MST 拆分为两个任意子集。这里有什么帮助吗？谢谢！

假设我对计算生成树有 3 种限制：

1. 约束度（例如：生成树中的一个节点最多只能连接 3 个其他节点）
2. 有界直径（例如：所有边的权重，一旦相加，不能超过 100）。
   2.1。如果可能，显示所有满足此条件的子树。
3. 两个都

有什么好的算法可以解决这个问题，不会让我发疯吗？我将不得不使用相当大的输入（1000 多个节点）来运行它，所以它的复杂性也不能太高。

来自维基百科。我知道外循环是 logV，因为您要加入集合。但随之而来的是内部循环。

如果您使用等价关系来跟踪集合，这意味着您只获取表示集合的元素，因此您无法确定两个集合之间权重最小的边，因为您没有所有元素. 如果您修改结构以保存对子项的引用，您仍然必须获取每个集合的所有子项。这意味着，更糟糕的情况是，每组 O(V/2) = O(V)。

之后，您仍然必须找到连接两者的最小边，这意味着遍历连接两个组件的所有边。所以你需要遍历每个节点，看看它的边是否连接到另一个组件中的元素，如果是，它是否小于你当前拥有的最小边。

意思是，一个迭代节点的外循环和一个迭代节点边缘的内循环 - O(V E)。由于它在 O(logV) 循环内，因此得到 O(logV V*E)。

现在，您似乎只需要遍历所有边，但是您将如何选择 2 个组件之间的最小边呢？我可以判断给定边是否连接不同组件中的节点，但我无法判断连接它们的哪一个具有最小权重。如果我得到一个重量最小的，它可能无法连接它们。