Thread: Prim's Algorithm

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

    Prim's Algorithm

    Hello there,
    I need you guys help on implementing Prim's algorithm..I have read about 40 pdf's and I am ashamed to find them confusing with their freaking symbols..I need some English algorithm..
    I understand I can use a priority queue or an array..
    I want to start with a priority queue but I don't understand how the pq should be stored..
    if the priority queue is a binary tree.does that mean the parent nodes must be smaller than the child nodes, since I am finding minimum weights?

    How do I represent the edges..the tree? Array or linked list?
    If you can provide intuitive steps in solving the problem..I would appreciate it.. thanks.
    You ended that sentence with a preposition...Bastard!

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    The standard library already has a priority queue, so no worries there.
    There are several ways to represent a graph, all with their advantages and disadvantages.

    One way is a matrix. Think of the rows as the source and columns as the destinations, for example. And in there, you can store the weight of the path.

    Another way is a linked list. You can create a structure for an edge which has a source and destination and a weight. Then connect your nodes by this edge. Store all edges related to a node (wherever they go) in a node, for example.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    I understand the complexity of making such an algorithm, but it is really a good practice to fully accomplish it.
    If it is too much then you can write some pseude-code or even just a description of a code. Or something to help you started.

    Or just elaborated with a more concrete way your questions

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Having implemented this algorithm, including a graph, from scratch, I know how ... overwhelming this can be at first.
    I don't find it rather strange that one should be asking abstract questions like this.
    Anyway, good luck. Hopefully it should all fall into place after you've started fleshing it out.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    mmn..thanks for advise..I will just take in deep breaths and try something..if I get stuck will get back for help.
    You ended that sentence with a preposition...Bastard!

  6. #6
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    i only got as far as priority queue..which I am not sure what to do with it..
    am I right in thinking that the priority queue holds the vertices that are not part of the MST..
    what I don't get is how to set the vertices in order of priority as I am storing the vertices itself..and not the weight :S
    ...
    You ended that sentence with a preposition...Bastard!

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    What is your definition of a vertice? Is it a node? An edge?
    It all depends on how you built the graph. One approach may be to store the edges into a priority queue in order to sort them, then take the edge with least weight and connect it in the resulting tree.
    Obviously a priority queue will store things that are "most" important first. This will be calculated normally by the less than operator, so you simply have to define it for your edge in such case.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    yeah I have the queue that stores the nodes not part of the tree...and as you said I need to return one of the nodes in the queue that has the least weight..to me I would assume it would be at the top of the queue, as in the root..
    But I can't imagine how I would sift the edges in the queue according to their weight..
    i have an array that holds the weight..but how can I apply that array to the array in priority queue? That's my problem
    You ended that sentence with a preposition...Bastard!

  9. #9
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    A node has no weight. Only edges have weight. And the thing is that you only need to put them inside the priority queue to sort them because that's what a priority queue does. Sorts inserted entries according to their priorities.
    std::priority_queue also has a third type parameter that specifies what function to use for ordering the elements inside the queue.

    But you don't really need to store anything. The basic algorithm goes like this (IIRC):
    For every NODE
    Find the edge with least weight which is NOT known
    Add source node to target graph
    Add destination node to target graph
    Connect nodes in target graph with appropriate weight
    Repeat
    Last edited by Elysia; 03-26-2011 at 03:42 PM.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  10. #10
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    yeah correct that it is the edges that have weight..what I mean is..the priority queue stores the node that has the least weight connected to by the current node..
    I am not allowed to use priority queue from stl list..so I wrote one..
    but since it stores the nodes.. and I have a weight array..how do I return the node with node with minimum weight using the weight array..
    lol..this is frustrating..only if there wasn't so much Greek in the explanations
    You ended that sentence with a preposition...Bastard!

  11. #11
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    Ask yourself this: is it possible to store the edges? Because it is clear that we can easily compare which edge is more expensive than others.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  12. #12
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    yeah .. i tried that..but the problem is how would I know which vertex to return?
    Because the indices of the pq array, (as normally the indices represent the nodes)..and the weight it contains will not be related.
    What I tried before was storing an array of nodes holding the node and the edges..but the algorithms only store ints....
    You ended that sentence with a preposition...Bastard!

  13. #13
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Location
    Inside my computer
    Posts
    24,654
    First off, there is no need to keep an array of nodes. Attach them as you go. Connect your graph as you go.
    Secondly, C++ allows you to define semantics such as determining if one object is "less" than another by allowing you to overload operators. You could say that a node can be less than another node and sort them that way, but it doesn't really make sense for nodes.
    But it makes perfect sense for edges. If you make a class to represent an edge, you can make the edge know which two nodes it connects among other things. It makes things easier.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  14. #14
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    yeah..I will take a break..and try again..Hopefully I will get an epiphany..highly unlikely
    You ended that sentence with a preposition...Bastard!

  15. #15
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    Hello..so kwl I was able to solve Prim's algorithm the day I made this thread...
    It looks like it is working fine....but to all you who have implemented this using a priority queue..is there a point in resetting the cost of an edge to a minimum value?
    It doesn't make sense to me..as we might have to add the sum of all minimum cost edges to get the shortest spanning tree...
    I was looking at the pseudo-code my lecturer provided and it doesn't make sense when on removing the next vertex on the MST from priority queue and set the distance or cost array to -1 or -INT_MIN..
    what is the point in doing that haha? Once a vertex connecting another vertex with minimum edge is put on the MST array..it becomes a closed edge.. can some clarify this..I just don't see the point in doing that. Our lecturer said it acts as a safeguard in case we find another edge that has minimum cost...I don't understand that either..
    I want to fully understand the reason why he did that..before I go on to implementing Kruskal...
    Thanks for any help. Here is the code:

    Code:
    while(!pq->empty())
    	{
    	   newVertex = pq->pop() ;
    
    	  // distance[newVertex] = -1 ; Why do I set min cost to -1? Is it even necessary?
    	
    	   for(Node *t= arr[newVertex]->next ; t!=NULL;t=t->next)
    	   {
    		     
    		   if(t->weight < distance[t->data])
    		   {
    			   distance[t->data] = t->weight ;
    			   
    			   parents[t->data] = newVertex ;
    			
    			   if(visited[t->data]==0 )
    				{
    				        pq->insert(t->data) ;
    				   
    					visited[t->data]=1; 
    				}
    				else
    				{
    				        pq->siftUp(hPos[t->data]) ;
    
    				}
    
    			   pq->arr[hPos[t->data]] ;
    			 
    		   }
    
    		   
    	   }
    	   
    	   MSTTree[++currentIndex] = newVertex ;
    	}
    You ended that sentence with a preposition...Bastard!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Prim's Kruskal Algorithm
    By iamnew in forum C Programming
    Replies: 8
    Last Post: 06-20-2010, 09:51 AM
  2. Appropriate container for prim's algorithm
    By Elysia in forum C++ Programming
    Replies: 6
    Last Post: 05-10-2010, 01:20 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 03:00 PM
  4. prims algorithm
    By condorx in forum C Programming
    Replies: 0
    Last Post: 11-09-2003, 06:20 AM