-
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.
-
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.
-
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
-
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.
-
mmn..thanks for advise..I will just take in deep breaths and try something..if I get stuck will get back for help.
-
:( 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
...
-
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.
-
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
-
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
-
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
-
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.
-
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....
-
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.
-
yeah..I will take a break..and try again..Hopefully I will get an epiphany..highly unlikely
-
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 ;
}