# Proof of Correctness of Prim's algorithm [duplicate]

what is the reason for the correctness proof of Prim's Algorithm for the undirected case cannot carry over to the directed case?

Is it because of after any number of steps, $S$ might not be in a sub tree of an MST since it depends upon the direction of the edge of the directed graph, unlike the undirected one?

• What is $S$? You should make your question self-contained, as different presentations of the algorithm may use different names for the variables. Dec 31 '13 at 15:41
• This is very similar to your other question.
– Kaya
Dec 31 '13 at 18:43
– D.W.
Dec 31 '13 at 19:25
• @fudu Well, thanks for wasting my time writing that answer for you. The person who answered your previous question even got their example from the same source as me (I changed the weights from 5, 5, 6, 1 to 3, 3, 4, 1), so you could have found it with Google too. Jan 1 '14 at 2:11

The key question is, what do you mean by "spanning subtree" for a directed graph?

If you just want a subgraph that is an oriented tree (i.e., a graph obtained from an undirected tree by choosing exactly one direction for each edge) then use Prim's algorithm and ignore the edge directions.

The normal concept for directed graphs, as @tbirdal points out, is the arborescence. An arborescence is what you might call a "consistently oriented" tree there's some vertex $v$ such that every edge is directed away from $v$. However, note that not every directed graph contains a spanning arborescence: for example, take the graph with vertices $\{a, b, c, d\}$ and directed edges $\{(a,b), (c,b), (c,d)\}$.

Prim's algorithm keeps going until it's added every vertex but we've seen that this can't work for directed graphs. Furthermore, even for directed graphs that do contain an arborescence, the greedy scheme of Prim's algorithm isn't guaranteed to find it. Essentially, this is because you might have to choose a sequence of high-cost edges to gain access to a sequence of low-cost edges. For example (source), in the graph with vertices $\{a,b,c,d\}$ and weights $w(a,b)=w(b,d)=3$, $w(a,c)=4$, $w(c,d)=1$, the minimum spanning arborescence is $\{(a,b),(a,c),(c,d)\}$ with weight $8$ but Prim's algorithm starting at $a$ produces the arborescence $\{(a,b),(b,d),(a,c)\}$ (adding the edges in that order), which has weight $10$.

A graph has a spanning arborescence if, and only if, there is at least one vertex (a root) that sends a directed path to every other vertex – this includes all strongly connected digraphs. In such a graph, Edmonds' algorithm finds a minimum-cost spanning arborescence from a given root in quadratic time.

Prim's algorithm starts with an arbitrary vertex. If you arbitrarily pick a vertex in a directed graph, you might end up with a vertex which is a pure sink, not a source (in other words no directed edge exists from that vertex to any other). In such a case you cannot find a minimum spanning tree including all the vertices.

You might still argue that this is an MST, because it is how they would be defined for directed graphs. However, this would be an Arborescence rather than an MST and other algorithms are there to give you a solution for that.

• If the only problem was that the initial vertex might have no out-edges, you'd just modify the algorithm not to pick such edges. Dec 31 '13 at 15:39
• Sure, but this was just an example. There is no criteria to stop the same situation occuring during any stage. You simply end up not selecting the complete tree. Of course I'm speaking for Prim's algorithm only. Dec 31 '13 at 16:47