What is minimum spanning tree? Determine a railway network of minimal cost for the cities in the following graph using Kruskal's algorithm.
Ans: Minimum spanning tree in a connected weighted graph is spanning tree which has the smallest possible sum of weights of its edges.
We collect the edges in sorted order like this:
Select the edges (B,C),(D,F),(A,G),(C,D),(C,E).
After that we have option we may choose only one of (A,B) and (A,D), as selection of both makes a circuit. Assume we choose (A,B).
Similarly we may choose just only one of (G,H) and (F,H).Assume we select (F,H).
We Comprise a spanning tree as:
