Algorithms for updating minimal spanning trees
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 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.
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.
It seems to work but I can easily make this run in O(|V|) time, while the problem asks O(|E|) time. By the way we are authorized to ask for help from anyone so I'm not cheating : D Yes, something like that!
Unless you've been told it, I don't think the property that no MST edge can be the longest edge in a cycle is "obvious". Re your proof question: suppose such an MST containing e1 existed. Because e1 was originally part of a cycle, there must be some other edge in that cycle that connects these 2 components (proving this part is left as an exercise :-P) and which has weight My previous comment only concerns the case where the cycle contains a uniquely heaviest edge.It applies even if there were or will be multiple MSTs -- no MST can ever contain that edge.But I now realise that there's more work to do if the cycle doesn't have a uniquely heaviest edge...I'm not sure then, as you can't rule out any edges for sure. I came up with the same proof as you j_random_hacker and I see no problem with it even if there are multiple edges of the same weight.What confuses me is that I think I can prove that in 2.