插入新边时更新最小生成树
我在大学遇到过以下问题：
设G = (V, E)是一个成本为ce的（无向）图>= 0 在边 e ∈ E 上。假设您在G 中得到了一个最小成本生成树T。现在假设向G添加一条新边，连接两个节点v，tv ∈ V，成本c。
- 给出一个有效的算法来测试T是否仍然是最小成本生成树，并将新边添加到G（但不添加到树T） ）。让你的算法在 O(|E|) 时间内运行。你能在 O(|V|) 时间内完成吗？请注意您对使用什么数据结构来表示树 T 和图 G 所做的任何假设。
- 假设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
I've been presented the following problem in University:
Let G = (V, E) be an (undirected) graph with costs ce >= 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, tv ∈ V with cost c.
- 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.
- 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
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?
By the way we are authorized to ask for help from anyone so I'm not cheating :D
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
你的想法是正确的，但如果你以正确的方式存储树，你可以在最短路径搜索方面比 BFS 做得更好。
假设 T 中的一个节点 r 是根（如果您已在矩阵或邻接中标记了树边，则可以从那里选择任何节点和 BFS 来生成此结构 -列表图结构），每个其他节点都有一个父指针和一个深度计数。要在 T 中找到 a 和 b 之间的最短路径：
该算法有效性的证明留给读者作为练习。这与 BFS 一样是 O(|V|)，但通常也更快。在实践中，只有少数 MST 配置实际上需要 O(|V|) 时间。当然，生成父链接树需要 O(|V|) 时间，因此这仅在某些情况下有帮助，例如如果您使用 MST 构建算法，该算法在确定父链接树的过程中自然地创建此结构MST。
正如另一位评论者所说，请注意，如果图存在 MST，则它是连接的，因此 |V| <= |E|因此 O(|V|) < O(|E|)。
此外，要在 O(|V|) 时间内修复树，如果需要，只需找到循环上最长的边并将其删除，用新边替换它即可。使用父链接 MST 有效地完成此操作也是读者的一项练习。
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.
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:
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.
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|).
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.
我认为 BFS 就足够了。它的复杂度是 O(|V| + |E|) 但在一棵树 |E| 中小于|V|所以 O(2|V|) 就是 O(|V|)
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|)
我相信你的步骤
在T中查找从a到b的最短路径是一个顺序E操作。I believe your step
Find in T the shortest path from a to bis an order E operation.