How do deal with the following situations using Prim's algorithm?
-
01-11-2019 - |
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.
- Do we ever take the self loop? Why not?
Suppose we just moved from C to D
- 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
- What should we do if we enters an in-terminating loop?
No correct solution
Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange