Graph Theory37 sections · 1633 units
Open in Course

MST in Disconnected Graphs

(Handling multiple components)

If the graph is disconnected, there is no spanning tree.

Instead, you get a minimum spanning forest: one MST for each connected component. Kruskal handles this without changes. You will add fewer than n1n-1 edges. Each component gets its own tree. Count the edges you added to detect this case. Prim only explores one component from the starting node. If you want a spanning forest with Prim, run it from one node per component.