Search code examples
graph-algorithmgreedyprims-algorithm

Does Prim's algorithm checks graph connectivity by itself?

I have some questions.

1.do we have to check the graph's connectivity before passing it to prim's Algorithm or the the algorithm can take care of that?

  1. Does prim's algorithm always work correctly on negative edge weights?

  2. How can I use prim's algorithm to find spanning tree with no weights on its edges?

Solution

  • 1.) I believe the purpose of Prim's algorithm is to 'generate' a minimum spanning tree with the nodes that you give it. I suppose you do need to make sure that an edge does exist between any 2 nodes that you give it.

    2.) Prim's algorithm (and minimum spanning tree algorithms) should work correctly on negative edge weights

    3.) I don't think so. I suppose you could make all of them '1' or something, but I don't think that would result in a very meaningful minimum spanning tree.