Thread: Prim's Algorithm

I don't understand this. There is one graph, and one only. Each graph has N nodes. And each node has at least one edge.
So what is a vertex in this context?

Also, initializing the distance to the minimum seems dubious. If anything, it should be initialized to the maximum.

Hello Elysia,
a vertex is a node..I don't know why i call them vertex lol..you're right there is one graph..And has nodes that are connected to each other by edges...
Prim's algorithm says if i start at a random node i pick the next node connected to it that has the least cost, distance, weight whatever...and I check if this node is connected to other node and finding the minimum edge also including the parent node...
so the distance or cost array..stores the least amount of edge that is connected to this vertex since we're finding the minimum spanning tree..if we set it to maximum we will definitely find an edge that is smaller...we only set the distance to maximum at the initial start..maybe in the constructor...
but if a node is popped of the priority queue..it is part of the minimum spanning tree..so surely then there is no way it might get updated..if so then I can understand why distance[index] is set to -1 when it is popped off..but I can't see how it might get updated after it has been removed from the priority queue

In fact..in all the other pseudocode online..they never reset distance..which makes sense ha

I would say your entire code is confusing. You should make a Graph, Node and Edge class, and not store stuff in some global arrays.
There is, for example, no information whatsoever that says the distance from where (ie from what node) you are storing.

i have a parent array that does that...stores the information..
the distance array is sufficient for holding the MST..lol did you read the Prim's algorithm man?
you're starting to confusing me too! lol

well..I would've to say fair play for replying man..others just skim this thread lol :O

o_O
Yes, I did write Prim's algorithm a year ago, or so.
But your solution is confusing and under all criticism IMO.
Don't use arrays. There is no information as to what owns what here. Encapsulate! Abstract!

to be honest..OOP style is the least of my worries..as long as I get this algorithm working..
but when you were doing the Prim's did you ever after removing from the heap array..did you ever set the weight to a minimum value or so?
Any way here is one algorithm from the internet

Code:

While P is not empty:

	1. Select the next vertex u to add to the tree
			u = P.deleteMin()

	2. Update the weight of each vertex w adjacent to 		u which is not in the tree (i.e., w  P)
		 	If weight(u,w) < D(w),
				a. parent(w) = u
			  	b. D(w) = weight(u,w)
				c. Update the priority queue to reflect 
			       new distance for w

Lecturers algorithm..possibly from wikipedia

Code:

Prim_Sparse( Vertex s )
Begin
// G = (V, E)
for each v in V
dist[v] = INT_MAX (infinity)
parent[v] = 0 // treat 0 as a special null vertex
hPos[v] = 0 // indicates that v  heap
h = new Heap // priority queue (heap) initially empty
h.insert(s) // s will be the root of the MST
while (not h.isEmpty() ) // should repeat  |V|-1  times 
v = h.remove()  // add v to the MST
dist[v] = -dist[v] // marks v as now in the MST
for each u in adj(v)  // examine each neighbour u of v
if wgt(v, u) < dist[u]
dist[u] = wgt(v, u)
parent[u] = v
if u is not an element of the heap
h.insert( u)  
else 
h.siftUp( hpos[u])
end if
end for
end w
return parent

it doesn't say to reset the distance...:S

Here is how I would do it:

Code:

insert first node into prim tree
mark source node as known
for each node node in the graph
	for each edge edge in node
		if edge->destination is known, continue
		push edge into priority queue
	loop
	pop first edge in queue
	add target node to prim tree
	connect source node and target node in prim tree with the edge weight
	empty priority queue
	mark target node as known
loop

This is sort of how I have implemented Dijkstra.

heck what you have is similar to what most of the algorithms have written..i would just pest him about it later lol..hopefully you have done the Kruskal algo?
It looks like the hardest..for one I don't know how to create disjoint set :S

I was thinking a list containing a list of list..something like that..but no idea :S

I don't want the code..just need to brainstorm..if you don't mind

I haven't done Kruskal, but like any experienced programmer, reading an algorithm description is a must. I will take a look and see what I can propose.

I don't know about experienced lol...but if I can read it and not go crazy I like nearly did for Prim's..i say I'd be getting there :P
God..that Prim's was a b*tch at first...Thanks..
I will have a read and re-read of it myself

OK, this one is easy.

Code:

define a map org_to_krus to map node in original tree to node in kruskal's tree
for each node node in the graph
	add node to the kruskal tree
	store node in org_to_krus
	for each edge edge in node
		store edge in priority queue
	loop
loop
while edges in kruskal tree < nodes - 1
	pop edge from queue
	if edge->source does not have another edge and edge->dest does not have another edge
		add edge to kruskal tree
loop

Something like that, barring bugs.

wth! how is that freaking easy? lol :P..aargh I will go read it and come back to your pseudo-code..
what is a map_org_krus anyways?

It says so, doesn't it?

define a map org_to_krus to map node in original tree to node in kruskal's tree

Basically, when you add a map in the kruskal tree, you need to find it later, since the edges are associated with the nodes in the original tree.
So you put in the node in the original tree, and it gives you the node in the kruskal tree.

But you know, essentially the algorithm is this:
Take all the nodes in the original graph and insert them into the kruskal tree.
Now take all the edges in the original tree, sort them based on weight.
Now take one edge, check if it can be inserted into the kruskal tree, and if it can, do it.
Repeat until all nodes have one edge.

Basically, the condition for inserting it into the tree is that the nodes is connects must not already be connected.

ah yeah..I get you..I will have a crack at it..Thanks for your support Elysia...I will be back :P