# Non-trivial runs of Prim's algorithm

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?

• I have no idea what you are talking about; how can a graph use an algorithm? Please give a (literal) example of the phrase. Mar 26, 2013 at 11:59
• let's say we want to apply Prim's Algorithm to an example graph but the graph should result it in a non-trivial run of the Prim's algorithm. So I was hoping if anyone would give me an example or idea how to achieve this kind of graph.
– fudu
Mar 26, 2013 at 12:06
• @fudu Do you want to ask what a trivial run is? Or do you know how a trivial run is defined, but want to know examples of graphs that will require a trivial/non-trivial run of Prim's algorithm? Mar 26, 2013 at 14:13
• @Paresh The main thing I want to understand in here is how to come with an example graph that will require a trivial/non-trivial run of Prim's algorithm, of course it would be nice to know what is a trivial run from the Prim's algorithm point of view.
– fudu
Mar 26, 2013 at 14:20
• I don't think there is a popular definition of a "trivial run" of Prim's algorithm. So unless you specify how you define trivial for this algorithm, the question is vague. @Raphael proposes one definition before answering. Someone else might say a trivial run is where the globally smallest edge is also the next available edge to the algorithm. This way, a simple sorting of edges by weight would suffice. In short, if you are not sure what trivial means, you could try to relate it to the context in which you encountered this. Mar 26, 2013 at 14:28

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.