1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

First of all , MST of a connected graph is a subgraph with the following properties:
i. Spanning Tree: No cycles -> n-1 edges(easy to prove)
ii. If we sum up the weights, we get the lowest possible.

Prim's algorithm is a greedy algorithm, which means that we always choose the best choice in every step(greedy).

  1. From i, you can see that you never get self loops (acyclic).

  2. Yes, because it's the edge with the lowest weight not because it is the only edge in this moment from D to connect in E; there maybe exist another edge eg. C->E would have been the next choice had the weight between D->E is 5.

  3. No, it does not get to a non-terminating loop, you never choose the same edge again. Think like, there is a set S with all the edges that have not been discarded, after you choose the edge e then S is changed to S-e. In your example the best choice is to choose E->F.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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