更新最小生成树插入一个新的边缘时， [英] Updating a Minimum spanning tree when a new edge is inserted

问题描述

我一直$ P $在大学psented以下问题：

I've been presented the following problem in University:

让 G =（V，E）的是一个（无向）图与成本的 C <子>电子 的> = 0的边缘的电子的＆ISIN代码; 电子的。假设你将得到一个最低成本生成树的 T 的在的。现在假设一个新的边缘添加到的，连接两个节点的 v 的 T <子> v 的＆ISIN代码; V 的成本的 C 的。

Let G = (V, E) be an (undirected) graph with costs c_e >= 0 on the edges e ∈ E. Assume you are given a minimum-cost spanning tree T in G. Now assume that a new edge is added to G, connecting two nodes v, t_v ∈ V with cost c.

1. 提供一个有效的算法，以测试的 T 的仍然是最低成本生成树的新的边缘添加到的（而不是树的 T ）。及时作出O对你的算法运行（| E |）。你能做到这一点在O（| V |）的时间？请注意，您对什么数据结构来重新present树中的任何假设的 T 的和图形的。
2. 在假设的 T 的不再是成本最低的生成树。举一个线性时间的算法（时间为O（| E |））。更新树T到新的最低成本生成树

1. Give an efficient algorithm to test if T remains the minimum-cost spanning tree with the new edge added to G (but not to the tree T). Make your algorithm run in time O(|E|). Can you do it in O(|V|) time? Please note any assumptions you make about what data structure is used to represent the tree T and the graph G.
2. Suppose T is no longer the minimum-cost spanning tree. Give a linear-time algorithm (time O(|E|)) to update the tree T to the new minimum-cost spanning tree.

这是我找到了解决办法：

This is the solution I found:

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 |）时间。我失去了一些东西？

It seems to work but I can easily make this run in O(|V|) time, while the problem asks O(|E|) time. Am I missing something?

当我们有权要求任何人，所以我不会作弊的帮助方式：D

By the way we are authorized to ask for help from anyone so I'm not cheating :D

推荐答案

您已经有了正确的想法，但你可以比BFS的最短路径搜索，如果你存储树以正确的方式做的更好。

You've got the right idea, though you can do better than BFS for the shortest-path search if you store the tree the right way.

说一个节点的研究的中的 T 的是根（你可以选择从那里任何节点和BFS产生这种结构如果标记的树边的矩阵或邻接表图结构），和相互节点具有父指针和一个深度计数。要找到之间的在的最短路径和 B 的中的 T 的：

Say one node r in T is the root (you can pick any node and BFS from there to generate this structure if you have marked the tree edges in a matrix or adjacency-list graph structure), and each other node has a parent pointer and a depth count. To find the shortest path between a and b in T:

1. 在我们的在的是更深节点;互换如果需要的话。
2. 遍历父从的在的，直到 B 或研究的达成，存储路径遍历，标志着节点访问。
3. 如果你到达的 B 的，最短路径为走过。
4. 如果你到达的研究的，然后还从横向的 B 的根;如果你到达节点从的在的在遍历达成的研究的，停下来。加入两个，他们见面和你在的 T 的最短路径。

1. Let a be the 'deeper' node; swap if needed.
2. Traverse the parent links from a until either b or r is reached, storing the path traversed, marking the nodes visited.
3. If you reach b, the shortest path is as traversed.
4. If you reach r, then also traverse from b to the root; if you reach node reached in the traversal from a to r, stop. Join the two where they meet and you have the shortest path in T.

该方法的有效性的证明是留给作为练习读者。这是O（| V |）像BFS，而且一般会更快。只有少数的MST配置实际上将需要O（| V |）的练习时间。当然，产生父链接树需要O（| V |）的时间开始，所以在某些情况下，这只能帮助，例如，如果您使用的MST建设算法在确定过程中天然产生这种结构MST。

Proof of the validity of this algorithm is left as an exercise to the reader. This is O(|V|) like BFS, but will also generally be faster. Only a few MST configurations would actually require O(|V|) time in practice. Of course, generating the parent-link tree takes O(|V|) time to begin with, so this only help in some circumstances, such as if you use an MST-building algorithm that naturally creates this structure in the process of determining the MST.

作为另一评论者说，请注意，如果有一个的MST为一个图表它相连接，使得| V | ＆LT; = | E |因此O（| V |）＆LT; O（| E |）。

As another commenter said, note that if there is a MST for a graph it is connected, so |V| <= |E| and thus O(|V|) < O(|E|).

此外，为了固定O型树（| V |）时，如果需要的话，只要找出对周期最长边和取出，用新的边缘代替它。与父链接MST有效地这样做也是读者练习。

Also, to fix the tree in O(|V|) time, if needed, simply find the longest edge on the cycle and remove it, replacing it with the new edge. Doing this efficiently with a parent-link MST is also an exercise for the reader.

这篇关于更新最小生成树插入一个新的边缘时，的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！