Graph Theory37 sections · 1633 units
Open in Course

Recognizing MST

Minimum cost spanning

The signals are "connect all" and "minimum cost." That is the definition of MST.

You need exactly n1n-1 edges to connect n nodes. Kruskal's algorithm picks the cheapest edges that do not create cycles.

If the graph has multiple components after processing all edges, output "IMPOSSIBLE." Check the number of edges added. If you added fewer than n1n-1 edges after processing all available edges, the graph is disconnected and full connectivity cannot be achieved.