Prim's algorithm - Programmers Heaven

Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Prim's algorithm

Mukta_NSITMukta_NSIT Posts: 1Member
Hello

I have to write program in c/c++ for prim's algorithm to find minimum spanning tree from undirected graph. I am unable to think of any way of coding it. Please can anybody help me in this.

Regards
Mukta

Comments

  • BitByBit_ThorBitByBit_Thor Posts: 2,444Member
    : Hello
    :
    : I have to write program in c/c++ for prim's algorithm to find
    : minimum spanning tree from undirected graph. I am unable to think of
    : any way of coding it. Please can anybody help me in this.
    :
    : Regards
    : Mukta
    :

    From Wikipedia:
    [code]
    The algorithm continuously increases the size of a tree starting with a single vertex until it spans all the vertices.

    * Input: A connected weighted graph with vertices V and edges E.
    * Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew= {}
    * repeat until Vnew=V:
    o Choose edge (u,v) from E with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, choose arbitrarily)
    o Add v to Vnew, add (u,v) to Enew
    * Output: Vnew and Enew describe the minimal spanning tree
    [/code]
    http://en.wikipedia.org/wiki/Prim's_algorithm

    Basically what you do is follow these steps, translating each to code. For instance, the 'repeat until ...' step can be directly implemented using a while loop.
    Your biggest challenge is to store the vertices and edges. Vertices can just be an array of points, but the edges need to describe starting point, ending point and weight.
    I'll give you a little hint on how to do this:
    Number the points (vertices) in the graph on paper, then in your program you can use the number of each point to describe it.
    Then create in C/C++ a structure to hold 1) start point, 2) end point and 3) distance (basically the Edge structure). Create an array of these structures to hold all the information about the edges.
    After this start working on using what you have to execute Prim's algorithm.
    I suggest you familiarise yourself with the algorithm before you begin coding, as a good understanding of how and why it works can make it much easier.

    Good luck. I think I did a poor job explaining, but hopefully it'll get you started none the least.
    Best Regards,
    Richard

    The way I see it... Well, it's all pretty blurry
Sign In or Register to comment.