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

algorithm graph graph-algorithm prims-algorithm
user1472747 picture user1472747 · Mar 26, 2014 · Viewed 25k times · Source

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

David Eisenstat picture David Eisenstat · Mar 26, 2014

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.

Related questions

Explanation of Algorithm for finding articulation points or cut vertices of a graph

I have searched the net and could not find any explanation of a DFS algorithm for finding all articulation vertices of a graph. There is not even a wiki page. From reading around, I got to know the basic facts …

Read More
How to find if a graph is bipartite?

I have been trying to understand the bipartite graph. To my understanding it is a graph G which can be divided into two subgraphs U and V.So that intersection of U and V is a null set and union …

Read More
Algorithm for diameter of graph?

If you have a graph, and need to find the diameter of it (which is the maximum distance between two nodes), how can you do it in O(log v * (v + e)) complexity. Wikipedia says you can do this using …

Read More