minimal spanning tree

[oren tal]

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!

[bascule]

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.

[Sepiraph]

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