0
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ I have no idea what you are talking about; how can a graph use an algorithm? Please give a (literal) example of the phrase. $\endgroup$
    – Raphael
    Mar 26, 2013 at 11:59
  • $\begingroup$ 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. $\endgroup$
    – fudu
    Mar 26, 2013 at 12:06
  • 1
    $\begingroup$ @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? $\endgroup$
    – Paresh
    Mar 26, 2013 at 14:13
  • $\begingroup$ @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. $\endgroup$
    – fudu
    Mar 26, 2013 at 14:20
  • 1
    $\begingroup$ 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. $\endgroup$
    – Paresh
    Mar 26, 2013 at 14:28

1 Answer 1

1
$\begingroup$

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:

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.