0

Guyz please help me
Ive got a practical exam tomorrow can anyone give a simple coding for implementing prims algorithm. It accepts the vertices and cost and gives out minimum spanning tree. Please guyz. It must be very simple. It need not be perfect. It need not work for all cases.
This isnt a HW help. I know the concept but its urgent.

2
Contributors
2
Replies
6
Views
7 Years
Discussion Span
Last Post by Adak
0

Or can anyone explain this code?? I cant understand it

#include <iostream>
using namespace std;
int g[20][20],visited[20],d[20],p[20];
int v,e;
void creategraph()
{

    int i,j,a,b,w;
    cout<<"\nVertices: ";
    cin>>v;
    cout<<"\nEdges ";
    cin>>e;
    for(i=1;i<=v;i++)
        for(j=1;j<=v;j++)
            g[i][j]=0;
    for(i=1;i<=v;i++)
    {
        p[i]=visited[i]=0;
        d[i]=32767;
    }
    for(j=1;j<=e;j++)
    {
        cout<<"\nEnter (a,b) and cost\n";
        cin>>a>>b>>w;
        g[a][b]=g[b][a]=w;
    }
}
void prim()
{

    int current,totalvisited,mincost,i,min;
    current=1;
    d[current]=0;
    totalvisited=1;
    visited[current]=1;
    while(totalvisited!=v)
    {
        for(i=1;i<=v;i++)
        {
            if(g[current][i]!=0)
                if(visited[i]==0)
                    if(d[i]>g[current][i])
                    {
                        d[i]=g[current][i];
                        p[i]=current;
                    }
        }
        min=32767;
        for(i=1;i<=v;i++)
        {
            if(visited[i]==0)
            if(d[i]<min)
            {
                min=d[i];
                current=i;
            }
        }
        visited[current]=1;
        totalvisited++;
    }
    mincost=0;
    for(i=0;i<=v;i++)
        mincost+=d[i];
    cout<<"\nMin cost ="<<mincost;
    cout<<"\nMin span Tree: ";
    for(int i=2;i<=v;i++)
        cout<<"\nVertex "<<i<<" is connected to "<<p[i];
}
int main()
{
    int i;
    creategraph();
    prim();
    return 0;
}
0

Sorry. Prim's algo is beyond me. That program doesn't look too difficult to follow through in a debugger, step by step.

Good luck. ;)

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.