Question

This question already has an answer here:

Does Kruskal's and Prim's algorithm work on directed graphs? I want the two algorithms to find a minimum spanning tree. For further enlightenment, I would like to know what other problems Kruskal's and Prim's can solve. So far, I only know they can solve minimum spanning trees. If it turns out there are an infinite number of problems Kruskal's and Prim's can solve, then no need to list all of them. I am learning this by myself and so far I only know one problem the two algorithms can solve.

I think that Prim's will not work because it is possible to have a node that points outwards to other nodes. If this central node is not chosen, then Prim's will be unable to give the MST including all the children.

I wonder if Kruskal's works. . . My counter example is a central node where all the children of the central node point to this central node. Running Kruskal's algorithm, we would get an MST that is not a shortest path, since we do not have path.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top