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.
1 Answer
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.
-
2$\begingroup$ This is not just a technicality; this is fundamental. The notion of a MST is not well-defined for a directed graph, so it doesn't even make sense to ask whether applying Prim's algorithm to a directed graph produces a MST. But the original question seems a bit confused, and hopefully the last paragraph will help the original poster a lot. $\endgroup$– D.W. ♦Dec 26, 2013 at 22:05
-
$\begingroup$ @D.W. Right you are, I edited the question to further emphasize this fact. $\endgroup$– KayaDec 27, 2013 at 1:19
G
which satisfies the hypotheses (i.e. connected, weighted). Do you wish to discard one of these properties? $\endgroup$G
is a connected, weighted graph. From these assumptions it then lays out a chain of logical implications (each founded on some other known result in mathematics) which lead to the conclusion that Prim's algorithm applied toG
yields the minimum spanning tree ofG
. SinceG
was chosen arbitrarily among all connected, weighted graphs this proof asserts that there are no counterexamples within this class. As I understand your question there can be no answer. $\endgroup$