What does it mean when we say that a run of Prim's algorithm is trivial? What are example graphs for either case, that is with and without trivial runs?
Asked By : fudu
Answered By : Raphael
Prim's algorithm greedily chooses the smallest edge leaving the set of already connected nodes (until all nodes are connected).
It is not clear what "non-trivial run" means here; I propose this: a run of Prim is trivial if in every step, it can choose the smallest available edge. This would happen on linear chains, for instance.
With this "definition", a non-trivial run is one during which the algorithm can not choose a cheap edge because it would create a cycle, but has to take a more expensive one. Here is an example graph:
[source]
If you start the algorithm with $A$, edge $\{B,C\}$ would be the cheapest after having chosen $\{A,B\}$ and $\{A,C\}$, but it can not be chosen.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10804
0 comments:
Post a Comment
Let us know your responses and feedback