The Student Room Group

finding the minimum spanning tree of a graph (very basic)

algo2.png

the solution doesn't make sense to me. e.g. why choose 3 edges of 1 but only 2 of 3?

is there a set way of answering these questions?

ty in advance
Original post by shartos maximus
algo2.png

the solution doesn't make sense to me. e.g. why choose 3 edges of 1 but only 2 of 3?

is there a set way of answering these questions?

ty in advance


You choose the edges with lowest value without making a cycle

You can choose all the 1s without a cycle the you just need two of the 2s to complete the tree - any two of the 2s would work
Original post by shartos maximus
algo2.png
e.g. why choose 3 edges of 1 but only 2 of 3?


6 vertices only require 5 edges for a spanning tree, and since you're looking for a minimum, you prefer the "1" edges as long as they don't form a loop. So, 3 of weight 1, then only two more are required. And any 2 of the tree will complete the MST.


is there a set way of answering these questions?


You could apply something like Prim's algorithm - it would be a good starting point. A bit of thought and logic is required though.

Edit: Pre-empted whilst typing. :frown:

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you