[Solved]: Minimal Spanning tree and Prim's Algorithm

Problem Detail: 

Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.

Asked By : fudu

Answered By : Kaya

For any un-directed graph G that is connected and weighted Prim's algorithm will produce the MST of the graph. However if the graph is directed this does not hold, as an example consider this directed graph:

╔═╗        ╔═╗        ╔═╗ ║ ║---5--->║B║---5--->║ ║ ║ ║        ╚═╝        ║ ║ ║A║                   ║D║ ║ ║        ╔═╗        ║ ║ ║ ║---6--->║C║---1--->║ ║ ╚═╝        ╚═╝        ╚═╝ 

Starting with A Prim's algorithm would choose edges (A,B),(B,D),(A,C) total weight of 16. The MST (if it were undirected) however is given by the edges (A,B),(A,C),(C,D) with a total weight of 12.

I should also clarify that directed graphs do not have MSTs (as they are only defined for undirected graphs). The closest notion for directed graphs would be Arborescence and an example of an algorithm which solves this similar question for directed graphs is Edmonds' Algorithm.

Best Answer from StackOverflow

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