Question

Consider the following Graph

We want to generate the MST using Prim's algorithm.

Starting from node A, suppose we pick B as our next node, we see a self-loop that has less weight than the two other alternatives.

  1. Do we ever take the self loop? Why not?

Suppose we just moved from C to D

  1. D only has one edge connecting to E, under Prim's algorithm we will take that edge right?

Now we have travelled from C to D to E, now I am making a choice at E. By picking the edge with the lowest weight we are back at C and the loop from C, D, E continues on forever

  1. What should we do if we enters an in-terminating loop?

enter image description here

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top