1

这是消费税

假设给定图 G 的最小生成树 T（具有 n 个顶点和 m 个边）和一条权重为 w 的新边 e = (u, v)，我们将添加到 G。给出一个有效的算法来找到图 G + e 的最小生成树。你的算法应该在 O(n) 时间内运行以获得完整的信用。

我有这个想法：

In the MST, just find out the path between u and v. Then find the edge (along the path) with maximum weight; if the maximum weight is bigger than w, then remove that edge from the MST and add the new edge to the MST.

棘手的部分是如何在 O(n) 时间内做到这一点，而且我也被卡住了。

问题是如何存储 MST。在普通 Prim 算法中，MST 被存储为父数组，即每个元素都是相应顶点的父元素。

所以假设消费税给了我一个指示 MST 的父数组，我怎样才能在 O(n) 中释放上述算法？

首先，如何从父数组中识别 u 和 v 之间的路径？我可以为 u 和 v 设置两个祖先数组，然后检查共同的祖先，然后我可以获得路径，尽管是向后的。我认为对于这部分，要找到共同的祖先，至少我必须在 O(n^2) 内完成，对吧？

然后，我们有了路径。但是我们仍然需要找到沿路径的每条边的权重。由于我认为该图将使用 Prim 算法的邻接列表，因此我们必须执行 O(m)（m 是边数）来定位边的每个权重。

...

所以我认为不可能在 O(n) 中执行该算法。我错了吗？

4

2 回答 2

1

你的想法是对的。请注意，找到 和 之间的u路径v是O(n)。我假设你有一个parent array识别 MST。跟踪从utov或uto的路径（对于最大边缘）root vertex应该只需要O(n). 如果您到达root vertex，只需跟踪从v到u或的路径root vertex。

现在您有了来自 的路径u -> u1 ... -> max_path_vert1 -> max_path_vert2 -> ... -> v，删除边缘max_path_vert1->max_path_vert2（假设这大于添加的边缘）并反转父级u->...->max_path_vert1并标记parent[u] = v。

编辑：为了清楚起见，更多解释

请注意，在 MST 中，任何一对顶点之间都只有一条路径。因此，如果您可以从u->y和追踪，那么您最多v->y只能追踪到n顶点。如果您跟踪了多个n顶点，则意味着您访问了两次顶点，这在 MST 中不会发生。好的，现在希望您确信从u->y和跟踪它是 O(n) v->y。一旦你有了这些路径，你就建立了一个从u->v. 你怎么看？我假设这是一个无向图，因为为有向图查找 MST 本身就是一个不同的概念。对于无向图，当您有一条来自 的路径时，您就有一条来自x->y的路径y-x。所以，u->y->v存在。您甚至不需要从 追溯y->v，因为 for 的权重v->y与 的相同y->v. u->y当您从和跟踪时，只需找到具有最大权重的边v->y。

现在在 O(1) 中寻找边权重；您如何存储当前的重量？邻接表还是邻接矩阵？对于 O(1) 访问，以存储父顶点数组的方式存储它。所以，weight[v] = weight(v, parent[v])。因此，您将拥有 O(1) 访问权限。希望这可以帮助。

于 2012-05-01T22:12:11.440 回答
0

好吧-您的解决方案是正确的。

但是关于实现，我不明白为什么要使用 G 而不是 T 来查找 u 和 v 之间的路径。使用 T 中的任何搜索遍历来查找 u 和 v 之间的路径，将为您提供 O(n)。- 也就是说，您可以假设 v 是根并执行深度优先搜索算法[在这种情况下，您必须假设 v 的所有邻居都是孩子] - 一旦找到 u，就停止 DFS - 然后，堆栈中的节点对应于 u 和 v 之间的路径。

之后很容易找到路径中每条边的成本 (O(n))，删除/添加边也很容易。总共 O(n)。

这有什么帮助吗？

或者，也许你得到 O(n^2) - 根据我的理解 - 因为你在 O(n) 中访问 T 中的顶点 v 的子级 - 在这里，你必须将你的数据结构呈现为映射数组，以便成本降低到 O(1)。[例如，{a,b,c,u,w}（顶点）-> {0,1,2,3,4}（顶点索引）。

于 2012-05-01T22:15:49.350 回答