Thread: Vague understanding about Prim's

  1. #1
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629

    Vague understanding about Prim's

    Hi,
    It is very clear how Kruskal algorithm prevents a cycle when finding the minimum spanning tree.
    Weird thing is I have implemented Prims algorithm, but I can't tell for the life of me what actually chooses a unique edge.
    I think it is due to the fact that we check if a node has not been inserted into the heap. So all the nodes in the heap are open nodes, but the if they're part of the MST we close the node by marking it as visited.
    So we only insert once into the heap.
    Can anyone clarify this..I was just writing the report and I was like..hold on..W*F?

    Code:
         if(u not in heap)
               pq.insert(u) //does the line prevent a cycle forming? pq is a priority queue
         else 
             siftup(hpos[u])
    Last edited by Eman; 04-12-2011 at 11:08 AM.
    You ended that sentence with a preposition...Bastard!

  2. #2
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    I'm not sure if it's going to make sense when I put it like this, but if a node is already in the MST, a circular graph should be impossible because it is either the child of some other node, or it is a parent of some other node. If it is a parent, it will be connected by a vertex on the same level as another node that is of equal or less weight (which is why you sift up existing nodes).

  3. #3
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    I think I understand what you're saying..
    I was thinking I insert into the heap once because if we don't we risk visiting a node twice.
    If a node is already part of the MST, but another node connected happens to have a lesser distance..if we do not do a check it will insert the visited node, change its parent to be incorrect..and at some later point pop the visited node out again. Which is wrong, as that forms a cycle.
    I had to step through the algorithm again..not sure?
    You ended that sentence with a preposition...Bastard!

  4. #4
    Lurking whiteflags's Avatar
    Join Date
    Apr 2006
    Location
    United States
    Posts
    9,613
    Wait I'm being confusing... yes, you understand now.

    It's not that we are afraid of visiting the node twice in the algorithm, because every vertex will be tested.

    But if you did insert a node twice, it would be wrong, since that forms a cycle somewhere in the graph (the same node was copied into the MST twice and now has two different parents).
    Last edited by whiteflags; 04-12-2011 at 01:30 PM.

  5. #5
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    Thank you man..now I can continue with this darn report
    You ended that sentence with a preposition...Bastard!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prim's Algorithm
    By Eman in forum C++ Programming
    Replies: 28
    Last Post: 03-29-2011, 01:19 PM
  2. Some vague problem about visual studio
    By hugoguan in forum C Programming
    Replies: 5
    Last Post: 01-14-2011, 11:57 PM
  3. Prim's algorithm
    By iamnew in forum C Programming
    Replies: 1
    Last Post: 06-06-2010, 07:02 AM
  4. vague title, self imflamatory...
    By doubleanti in forum A Brief History of Cprogramming.com
    Replies: 17
    Last Post: 03-14-2002, 09:30 AM