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.

  • $\begingroup$ Which problem do you want the algorithms to solve on directed graphs? Minimum Spanning Arborescence? $\endgroup$
    – Pål GD
    May 10 '15 at 13:58
  • $\begingroup$ Good point. I adjusted my question. I did not even know the two algorithms can solve different problems. . . $\endgroup$
    – user26658
    May 10 '15 at 17:13

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.


Not the answer you're looking for? Browse other questions tagged or ask your own question.