algorithm - graph - 添加新边后更新最小生成树的实现

Question

这是一个消费税

Suppose we are given the minimum spanning tree T of a given graph G (with n vertices and m edges) and a new edge e = (u, v) of weight w that we will add to G. Give an efficient algorithm to find the minimum spanning tree of the graph G + e. Your algorithm should run in O(n) time to receive full credit.

我有这样的想法:

在MST中，只需找出u和v之间的路径。然后找到(沿着路径)具有最大权重的边；如果最大权重大于 w，则从 MST 中删除该边并将新边添加到 MST。

---

棘手的部分是如何在 O(n) 时间内完成此操作，我也被卡住了。

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

那么假设消费税给了我一个指示 MST 的父数组，我如何才能在 O(n) 中发布上述算法？

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

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

...

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

Answer 1

你的想法是对的。请注意，找到 u 和 v 之间的路径是 O(n)。我假设您有一个 parent array 标识 MST。跟踪从 u 到 v 或 u 到 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 和 v->y 跟踪是 O(n)。一旦你有了这些路径，你就建立了一条来自 u->v 的路径。你看怎么样？我假设这是一个无向图，因为为有向图寻找 MST 本身就是一个不同的概念。对于无向图，当您有一条来自x->y 的路径时，您就有一条来自y-x 的路径。所以，u->y->v 存在。您甚至不需要从 y->v 追溯，因为 v->y 的权重将与 y->v< 的权重相同。当您从 u->y 和 v->y 追踪时，只需找到具有最大权重的边即可。

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