20

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

令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 更新为新的最小成本生成树。

这是我找到的解决方案：

Let e1=(a,b) the new edge added
Find in T the shortest path from a to b (BFS)
if e1 is the most expensive edge in the cycle then T remains the MST
else T is not the MST

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

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

4

3 回答 3

8

您的想法是正确的，尽管如果您以正确的方式存储树，那么在最短路径搜索方面您可以做得比 BFS 更好。

假设T中的一个节点r是根（如果您在矩阵或邻接列表图结构中标记了树边，则可以从那里选择任何节点和 BFS 来生成此结构），并且每个其他节点都有一个父指针和深度计数。要在T中找到a和b之间的最短路径：

  1. 让a成为“更深”的节点；如果需要交换。
  2. 从a遍历父链接，直到到达b或r，存储遍历的路径，标记访问的节点。
  3. 如果你到达b，最短的路径就是遍历的。
  4. 如果你到达r ，那么也从b遍历到根；如果在从a到r的遍历中到达节点，请停止。加入他们相遇的两个地方，你就有了T中的最短路径。

该算法有效性的证明留给读者作为练习。这和 BFS 一样是 O(|V|)，但通常也会更快。实际上，只有少数 MST 配置实际上需要 O(|V|) 时间。当然，生成父链接树需要 O(|V|) 时间，所以这仅在某些情况下有帮助，例如，如果您使用 MST 构建算法，在确定MST。

正如另一位评论者所说，请注意，如果图的 MST 是连接的，那么 |V| <= |E| 因此 O(|V|) < O(|E|)。

此外，要在 O(|V|) 时间内修复树，如果需要，只需找到循环中最长的边并将其删除，并用新边替换它。使用父链接 MST 有效地执行此操作也是读者的练习。

于 2010-04-29T22:38:23.510 回答
0

I think a BFS would suffice. And it's complexity is O(|V| + |E|) but in a tree |E| is less than |V| so it's O(2|V|) that is O(|V|)

于 2010-04-29T07:38:19.983 回答
-1

我相信你的步骤Find in T the shortest path from a to b是一个订单E操作。

于 2010-04-28T19:52:07.037 回答