Why can't Prim's or Kruskal's algorithms be used on a directed graph?

Question

Prim's and Kruskal's algorithms are used to find the minimum spanning tree of a graph that is connected and undirected. Why can't they be used on a graph that is directed?

Answer 1

It's a minor miracle that these algorithms work in the first place -- most greedy algorithms just crash and burn on some instances. Assuming that you want to use them to find a minimum spanning arborescence (directed paths from one vertex to all others), then one problematic graph for Kruskal looks like this.

 5   --> a  /   / ^ s   1| |2  \   v /   --> b  3 

We'll take the a->b arc of cost 1, then get stuck because we really wanted s->b of cost 3 and b->a of cost 2.

For Prim, this graph is problematic.

 5   --> a  /   / s   1|  \   v   --> b  3 

We'll take s->b of cost 3, but we really wanted s->a of cost 5 and a->b of cost 1.

Answer 2

Prim's and Kruskal's algorithms output a minimum spanning tree for connected and "undirected" graphs. If the graph is not connected, we can tweak the algorithms to output minimum spanning forests.

In Prim's algorithm, we divide the graph in two sets of vertices. One set of the explored vertices which have already formed a MST (Set 1) and another set of unexplored vertices which will eventually join the first set to complete "spanning" (Set 2). At each instant, we select a minimum weighted edge in the cut joining the two disjoint sets. If there is no directed edge from explored nodes of the MST to the remaining unexplored nodes, the algorithm gets stuck even though there are edges from unexplored nodes to explored nodes in the MST.

In Kruskal's algorithm, the idea is to sort the edges in ascending order by their weight and pick them up in order and include them in the MST of explored nodes/edges if they do not already form a cycle with any explored nodes. This is done using the Union-Find data structure. But detection of cycles for directed graphs fails with this method. For example, a graph containing edges [1->2] [2->3] [1->3] will be reported to contain a cycle with the Union-Find method.

So Prim's fails because it assumes every node is reachable from every node which, though valid for undirected graphs, may not be true for digraphs. Kruskal's fails because of failure to detect cycles and sometimes it is essential to add edges making cycles to satisfy the "minimum" weighted property of MST.

Also, in case of digraphs, MST doesn't make complete sense. Its equivalent for digraphs is "minimum spanning arborescence" which will produce a tree where every vertex can be reached from a single vertex.