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

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

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.