问题标签 [minimum-spanning-tree]

假设我们找到了一个最小生成树。现在，我们只需要 MST 中从 A 到 Z 的路径。我们如何在 O(n^2) 时间内做到这一点？

我们从根 A 开始。然后我们查看 Ax 形式的树中的所有边（其中 x 是任何顶点）。

然后，假设我们找到：AB、AC、AD 等......然后对于每一个，我们寻找形式的边：Bx、Cx、Dx......这显然不是 O(n^2)。

那么在给定 MST 的情况下，找到路径 A -> Z 的更好/有效方法是什么？

谢谢

我正在尝试通过在 MST 中添加新顶点来更新 MST。为此，我一直在关注 Chin 和 Houck 的“更新生成树”。 http://www.computingscience.nl/docs/vakken/al/WerkC/UpdatingSpanningTrees.pdf

论文中的一个步骤要求我在两个给定顶点之间的路径中找到最大的边。我的想法是找到顶点之间的所有可能路径，然后从路径中找到最大的边。我一直在尝试在 MATLAB 中实现这一点。然而，到目前为止，我一直没有成功。任何用于查找两个顶点之间的所有路径，甚至是两个给定节点/顶点之间路径中最大边的引导/清除算法都会受到欢迎。

作为参考，我想举一个例子。如果图形具有以下边 1-2、1-3、2-4 和 3-4，则 4 和 4 之间的路径为：

1) 4-2-1-3-4

2) 4-3-1-2-4

谢谢

我正在使用 C 语言中的 Prim MST，该函数采用邻接矩阵。考虑到重量当然在A[i][j].

假设我有一个前驱数组，可以追踪我到目前为止找到的最小边。 predecessor[u]=v{这也是最终的 MST}

现在我想修改当前A[i][j]矩阵并将权重更改为 1。也就是说，边（索引）也存在于前驱数组中。否则，我将其更改为零。

我该怎么做？这是我的解决方案：

优先级队列中的EXTRACT-MIN操作和操作之间的关系是什么？DECREASE-KEY我在使用 Prim 算法的最小跨度问题的讲座中遇到了这个问题。

麻省理工学院的教授在视频中的 01:07:16 秒时提到了它，但我不明白。有人可以帮我解决这个问题吗？

PS：否则我对我对优先队列的理解感到满意。

在这个关于最小生成树的 Prims 算法的 MIT 视频中，教授π[v] ←u在 71:16 秒时解释了这一点。但我不明白为什么我们需要这一步。这个符号 π[v] ←u实际上是什么意思？此外，算法中的最后一行是什么意思？源码中给出的整个算法如下：

如果有一个图 G 有 V 个顶点和 E 个边，并且我已经知道 G 的最小生成树 T，然后如果从 E 中取出一些边并且它们的权重增加了 50，那么这些边可能会也可能不会在最小生成树中。牢记上述情况，有没有办法在线性时间内重新生成新的最小生成树？注意：权重被修改的边数只有 5 个。

设G = (V,E)为无向图。让w(e)是一个具有正权重的加权函数。让是关于T的最小生成树。Gw

给定一组边S，其中S是 的子集E(G)，定义一个新的加权函数Q，Q(e) = w(e)如果e不在S，Q(e) = w(e)+100如果e在S。设计一个算法，接受作为输入 , ,G和一个集合，并输出一个最小生成树 wrt 。使其及时运行。TwS|S| = 10QO(V+E)

好的：自从我最初提出这个问题以来，我了解到的是，对 MST 进行分区是为了“分解”一条边，这会产生两个独立的组件，每个 MST 的顶点都是它们自己组件中的顶点。因此，在这个问题中，S 中的边可能会将 MST 分解为更小的 MST（11，对吗？）。我必须找到将一个组件连接到另一个组件的最轻的边缘。

我的计划是从一个顶点开始并使用 BFS 进行扩展，直到我涵盖所有这些组件。对于组件中的每个 u，u.color = black. 然后，我返回并再次用 BFS 覆盖组件，这次找到所有连接到非黑色顶点的边，因此不包含在组件中，并穿过现有的切口。与这些边相对的顶点被放置在队列 R 中。一旦我完成，我u = RemoveMin(R)就是运行O(lgE)。因为它只会在我每次覆盖一个组件时被调用，所以它总体上运行的最大值是10*O(lgE)，仍然是O(lgE). 因此，一旦删除 u，我就会对新组件执行 BFS，以便该组件中的所有 u.color = black。我再次遍历所有黑色顶点，以便我可以将所有带有更新键的白色顶点排队到 R 中。我做u = RemoveMin(R).

所以我真的认为这是可行的并且是可以证明的。任何人都可以提出类似的建议吗？

任何帮助，无论多么小，都将不胜感激。

嗨，我正在做一些测试准备，我需要弄清楚 b 和 c 部分。我知道 a 部分是正确的，我可以证明这一点，但是找到 b 和 c 部分的算法目前让我望而却步。

解决以下问题以获得最小瓶颈树，其中具有最大成本的边被称为瓶颈。(a) G 的每个最小瓶颈生成树都是 G 的最小生成树吗？证明你的主张。

(b) 对于给定的成本 c，给出一个 O(n+m) 时间的算法来找出 G 的最小瓶颈生成树的瓶颈成本是否不大于 c。

(c) 找到一种算法来找到 G 的最小瓶颈生成树。

提前感谢任何可以帮助我的人

我将在下周完成我书中的所有练习来修改课堂测试，我对这个子图问题感到非常困惑。

目前，我的想法使我相信，由于我们已经有一个最小生成树 G，因此由于我们在该最小生成树中存在子节点，因此 G' 必须存在。就条件而言，我有点茫然。

如果 X' 的节点集和边集分别是 X 的节点集和边集的子集，则图 X' 是图 X 的子图。让我们将 (V,T) 作为 G 的最小生成树，并且 G'=(V',E') 是 G 的连通子图。

(a)证明(V′,E′∩T)是G′的最小生成树的子图。

(b) 在什么条件下 (V′,E′∩T) 是 G′ 的最小生成树？证明你的主张。

提前致谢！

有人可以向我解释为什么使用相邻矩阵的 Prim 算法会导致时间复杂度为0 吗？O(V2)