Problem Detail: 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.
[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 Ask a Question Download Related Notes/Documents
