I was thinking that Prim's algorithm won't work with a disjointed graph. But maybe it doesn't have to.

When we're asking to find the minimum spanning tree of a graph, is it implicit that the graph will always be connected?

  • 1
    $\begingroup$ Yes. The graph must be connected. $\endgroup$ – David G. Stork Jul 12 at 7:53
  • 2
    $\begingroup$ For a disjointed graph you can't have a spanning tree. If you want a subgraph that spans the entire disjointed graph it's called a spanning forrest. $\endgroup$ – limeeattack Jul 12 at 9:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.