Like Tree1Likes

Prim's Algorithm

This is a discussion on Prim's Algorithm within the C++ Programming forums, part of the General Programming Boards category; I don't understand this. There is one graph, and one only. Each graph has N nodes. And each node has ...

  1. #16
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    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.
    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.

  2. #17
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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
    Last edited by Eman; 03-29-2011 at 01:28 PM.
    You ended that sentence with a preposition...Bastard!

  3. #18
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    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.
    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.

  4. #19
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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
    You ended that sentence with a preposition...Bastard!

  5. #20
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    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!
    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.

  6. #21
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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
    You ended that sentence with a preposition...Bastard!

  7. #22
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    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.
    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. #23
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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
    You ended that sentence with a preposition...Bastard!

  9. #24
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    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.
    Eman likes this.
    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. #25
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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
    You ended that sentence with a preposition...Bastard!

  11. #26
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    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.
    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. #27
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    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?
    You ended that sentence with a preposition...Bastard!

  13. #28
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    22,915
    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.
    Last edited by Elysia; 03-29-2011 at 02:15 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.

  14. #29
    The Dragon Reborn
    Join Date
    Nov 2009
    Location
    Dublin, Ireland
    Posts
    629
    ah yeah..I get you..I will have a crack at it..Thanks for your support Elysia...I will be back :P
    You ended that sentence with a preposition...Bastard!

Page 2 of 2 FirstFirst 12
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, 10:51 AM
  2. Appropriate container for prim's algorithm
    By Elysia in forum C++ Programming
    Replies: 6
    Last Post: 05-10-2010, 02: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, 04:00 PM
  4. prims algorithm
    By condorx in forum C Programming
    Replies: 0
    Last Post: 11-09-2003, 06:20 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21