Consider the graph given below (edges with weights): A-C = 6, A-E = 4, A-D = 2, A-G = 3, C-G = 2, C-F = 5, C-B = 4,
Consider the graph given below (edges with weights):
A-C = 6, A-E = 4, A-D = 2, A-G = 3, C-G = 2, C-F = 5, C-B = 4,
D-E = 5, D-G = 4, D-B = 4, G-B = 3, B-F = 4
Use Kruskal's algorithm to find a minimal spanning tree for the graph. The list of edges of the tree in the order in which they are choosen it?
Show answerHide answer
Correct answer: (C) GC, AD, GB, GA, BF, AE
Explanation
Kruskal's algorithm picks edges in increasing order of weight while avoiding cycles: GC = 2, AD = 2, GB = 3, GA = 3, then BF = 4 and AE = 4. So the order is GC, AD, GB, GA, BF, AE. Note: more than one order is possible since edge weights are repeated.