oren tal Posted May 1, 2007 Share Posted May 1, 2007 I need help in design algoritem that check for a given Graph if a minimal spanning tree exist without a specific edge. Mean that for the original graph you find a minimal spannig tree and that spanning tree not include the edge and it is minimal spanning tree of the graph that do include the edge. The algorithm must run in O(|V| + |E|) when V - vertics and E - edge Thank for any help! Link to comment Share on other sites More sharing options...
bascule Posted May 4, 2007 Share Posted May 4, 2007 Have you looked at Dijkstra's minimal spanning tree algorithm? There are others as well. You don't need to design an algorithm. This problem has been solved many times before. Link to comment Share on other sites More sharing options...
Sepiraph Posted May 4, 2007 Share Posted May 4, 2007 Always check wikipedia & google http://en.wikipedia.org/wiki/Minimal_spanning_tree Dijkstra's minimal spanning tree algorithm (or a variation of it) is used in OSPF for linked-state protocol in router, of which the internet depends on. http://en.wikipedia.org/wiki/OSPF Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now