[Solved]: Kruskal's and Prim's algorithm

Problem Detail: 

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.

Asked By : user26658

Answered By : OrWn

By definition MST or Minimal spanning tree is defined on undirected graph only!

But if you are really want to (and I wander why) You can "make" Kruskal's algorithm work on it ,but you have to make sure you are ignoring loops because otherwise if you got a loop with small weight the algorithm will count it on the "MST" (because it isn't really MST).

Regarding to Prim's algorithm I can't see a way you cane make this work on directed graph.

I don't know other uses of Kruskal's and Prim's and I don't believe there are. Usually you make a slight changes on the algorithm in order to make them do something slight different.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42371