Test yourself
Consider the following graph..
After three iterations, which are the edges which have been included into the MST ?
Which of the following edges will be included in the resulting MST ?
Kruskal's algorithm helps compute the minimum spanning tree of a graph.
A minimum spanning tree is a subset of a connected undirected graph that connects all vertices, and has the minmum possible weight of any subset that satisfies these conditions.
1) Arrange the edges of he graph in non-decreasing order.
2) Consider each edge in that order individually.
3) If including the edge in the MST would create a cycle, ignore it and move on the next edge.
4) If not, include it in the MST and move on to the next edge.
5)Terminate when all the edges have been considered.