CODEWITHSUNDEEP
algorithmgraph
Slowpoe
Slowpoe

Reputation: 41

Validating Minimum Spanning tree in Graph

I am trying to validate Minimum spanning tree (T = V,ET) of a Graph (G= V, E). Is there a way to Verify it like return true is its a MST other wise return False? Thanks

Upvotes: 0

Views: 150

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59303

Probably the easiest way is to use Kruskal's algorithm to generate a MST. When you sort the edges, sort edges from the given tree before all others of the same weight.

If the given tree is a MST, then Kruskal's algorithm will then generate exactly the same tree.

Upvotes: 1

Related Questions