Topic: Algorithms
Find the minimum spanning distance and the corresponding number of edges for the following graph
- A. 10,3
- B. 11,4
- C. 15,4
- D. 28,7
Answer: B. 11,4
Explanation: Using Kruskal's algorithm on the given graph with edges AB=1, DE=2, BE=3, BD=4, BC=5, CE=6, AC=7. We select edges in increasing order of weight avoiding cycles: Select AB (1), DE (2), BE (3). The next edge is BD (4), but it forms a cycle (B-E-D-B), so we skip it. We select BC (5). All 5 nodes (A, B, C, D, E) are now connected. Total edges = 4. Minimum spanning distance = 1 + 2 + 3 + 5 = 11.