Prim's algorithm and Kruskal's algorithm program help

Question

thinkerman 0 Newbie Poster

12 Years Ago

Hello. I'm having trouble with creating a program based on Prim's algorithm. This is the program and got the following error:

#include<iostream>
#include<stdio.h>
#include<conio.h>
using namespace std;
int weight[20][20],visited[20],d[20],p[20];
int v,e;

void creategraph()
{
int i,j,a,b,w;
cout<<"\nEnter number of vertices";
cin>>v;
cout<<"\nEnter number of edges";
cin>>e;
for(i=1;i<=v;i++)
  for(j=1;j<=v;j++)
    weight[i][j]=0;
for(i=1;i<=v;i++)
{
  p[i]=visited[i]=0;
  d[i]=32767;
}
for(i=1;i<=e;i++)
{
  cout<<"\nEnter edge a,b and weight w:";
  cin>>a>>b>>w;
  weight[a][b]=weight[b][a]=w;
}
}

void prim()
{
int current,totalvisited,mincost,i;
current=1;d[current]=0;
totalvisited=1;
visited[current]=1;
while(totalvisited!=v)
{
  for(i=1;i<=v;i++)
  {
    if(weight[current][i]!=0)
      if(visited[i]==0)
    if(d[i]>weight[current][i])
    {
      d[i]=weight[current][i];
      p[i]=current;
    }
  }
  mincost=32767;
  for(i=1;i<=v;i++)
  {
    if(visited[i]==0)
      if(d[i]<mincost)
      {
    mincost=d[i];
    current=i;
      }
  }
  visited[current]=1;
  totalvisited++;
}
mincost=0;
for(i=1;i<=v;i++)
  mincost+=d[i];
  cout<<"\nMinimum cost="<<mincost;
cout<<"\nMinimum span tree is";
for(i=1;i<=v;i++)
  cout<<"\nVertex "<<i<<" is connected to"<<p[i];
}

main()
{
creategraph();
prim();
getch();
}

error C4430: missing type specifier - int assumed. Note: C++ does not support default-int

I did not create a program for Kruskal's algorithm because I want to focus on the Prim's program first. Thanks in advance.

c++

8 Contributors
14 Replies
1K Views
4 Years Discussion Span
Latest Post 7 Years Ago Latest Post by Aiman_1

Ancient Dragon 5,243 Achieved Level 70

12 Years Ago

line 71 must be int main()

np complete 8 Newbie Poster

12 Years Ago

If you want to follow Standard then replace #include<stdio.h> with #include<cstdio>

Ancient Dragon 5,243 Achieved Level 70

12 Years Ago

Just briefly looking at your program, on line 34, what's the value of m? Answer: undetermined because you failed to set its value to something (using an uninitialized variable).

Next problem is that arrays have valid indexes as 0, 1, 2, 3, ... N-1. Your loops should start at 0, not at 1, and continue until < N, not <= N.

Edited 12 Years Ago by Ancient Dragon

Bob 15 using namespace Bob

12 Years Ago

warning C4700: uninitialized local variable 'n' used line 39

 32.   int cost[10][10],i,j,k,n,c,visit,visited[10],l,v,count1,vst,p,dup1,dup2;

 39.  for(i=0;i<n;i++)

You're using n in an expression in line 39, for (i=0; i<n; i++), but it hasn't yet been initialised, so it holds an unknown garbage value. When i is compared with n, you're comparing i with whatever garbage value n holds. The compiler, understandably, is warning you of this potential problem, which if unresolved can lead to a bug and possible obscure behaviour.

Reply to this topic

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.

thinkerman 0 Newbie Poster · Answer 1 · 2012-09-16T23:57:08+00:00

Thanks for the solution Ancient Dragon. I'll try to create the program for Kruskal's Algorithm and post it here if I encounter any errors. I also replaced #include<stdio.h> with #include<cstdio>. Feel free to suggest any other changes as long as they don't radically change the output.

thinkerman 0 Newbie Poster · Answer 2 · 2012-09-23T18:12:30+00:00

Alright. It took me a while to make the program. Since Prim's algorithm and Kruskal's algorithm are similiar, I decided to use the Prim's algorithm code and rework it to use Kruskal's algorithm.

#include<iostream>
#include<cstdio>
#include<conio.h>
using namespace std;
int weight[20][20],visited[20],d[20],p[20];
int v,e;

void creategraph()
{
int i,j,a,b,w;
cout<<"Enter number of vertices: ";
cin>>v;
cout<<"\nEnter number of edges: ";
cin>>e;
for(i=1;i<=v;i++)
  for(j=1;j<=v;j++)
    weight[i][j]=0;
for(i=1;i<=v;i++)
{
  p[i]=visited[i]=0;
  d[i]=32767;
}
for(i=1;i<=e;i++)
{
  cout<<"\nEnter edge a, b and weight w: ";
  cin>>a>>b>>w;
  weight[a][b]=weight[b][a]=w;
}
}

void kruskal()
{
int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p,dup1,dup2;
for(k=1;k<=m;k++)1;
{
cin >>i >>j >>c;
cost[i][j]=c;
cost[j][i]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
visit=1;
while(visit<n)
{
v=31999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]!=31999 && cost[i][j]<v  && cost[i][j]!=-1)
{
int count =0;
for(p=1;p<=n;p++)
{
if(visited[p]==i || visited[p]==j)
count++;
}
if(count >= 2)
{
for(p=1;p<=n;p++)
if(cost[i][p]!=31999 && p!=j)
dup1=p;
for(p=1;p<=n;p++)
if(cost[j][p]!=31999 && p!=i)
dup2=p;

if(cost[dup1][dup2]==-1)
continue;
}
l=i;
k=j;
v=cost[i][j];
}
cout <<"edge from " <<l <<" to "<<k;
cost[l][k]=-1;
cost[k][l]=-1;
visit++;
int count=0;
count1=0;
for(i=1;i<=n;i++)
{
if(visited[i]==l)
count++;
if(visited[i]==k)
count1++;
} 
if(count==0)
visited[++vst]=l;
if(count1==0)
visited[++vst]=k;
}
}

int main()
{
creategraph();
kruskal();
getch();
}

I debug the program, input the vertices, edges, and weight and once I'm done, it says that there is an error and forced me to break the program. There is an arrow at line 40 saying that it will be the next statement that will be executed. I'm aware that I declared a lot of variables in void kruskal(). Could that be the problem? If so, which int variables should I use in void kruskal()? If not, then what can I do to fix the error?

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague · Answer 3 · 2012-09-23T20:24:43+00:00

It really helps to format your code so others can follow it. Formatting also helps you when you get an error like "end of file during compile" of "else without if"...

Also, conio.h is non-standard and should be avoided. You certainly don't need it in these programs.

TrustyTony 888 pyMod Team Colleague Featured Poster · Answer 4 · 2012-09-23T20:33:59+00:00

Agreed, WaltP. As example, here is what Code::Blocks AStyle plugin makes out of your code

#include<iostream>
#include<cstdio>
#include<conio.h>
using namespace std;
int weight[20][20],visited[20],d[20],p[20];
int v,e;

void creategraph()
{
    int i,j,a,b,w;
    cout<<"Enter number of vertices: ";
    cin>>v;
    cout<<"\nEnter number of edges: ";
    cin>>e;
    for(i=1; i<=v; i++)
        for(j=1; j<=v; j++)
            weight[i][j]=0;
    for(i=1; i<=v; i++)
    {
        p[i]=visited[i]=0;
        d[i]=32767;
    }
    for(i=1; i<=e; i++)
    {
        cout<<"\nEnter edge a, b and weight w: ";
        cin>>a>>b>>w;
        weight[a][b]=weight[b][a]=w;
    }
}

void kruskal()
{
    int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p,dup1,dup2;
    for(k=1; k<=m; k++)1;
    {
        cin >>i >>j >>c;
        cost[i][j]=c;
        cost[j][i]=c;
    }
    for(i=1; i<=n; i++)
        for(j=1; j<=n; j++)
            if(cost[i][j]==0)
                cost[i][j]=31999;
    visit=1;
    while(visit<n)
    {
        v=31999;
        for(i=1; i<=n; i++)
            for(j=1; j<=n; j++)
                if(cost[i][j]!=31999 && cost[i][j]<v  && cost[i][j]!=-1)
                {
                    int count =0;
                    for(p=1; p<=n; p++)
                    {
                        if(visited[p]==i || visited[p]==j)
                            count++;
                    }
                    if(count >= 2)
                    {
                        for(p=1; p<=n; p++)
                            if(cost[i][p]!=31999 && p!=j)
                                dup1=p;
                        for(p=1; p<=n; p++)
                            if(cost[j][p]!=31999 && p!=i)
                                dup2=p;

                        if(cost[dup1][dup2]==-1)
                            continue;
                    }
                    l=i;
                    k=j;
                    v=cost[i][j];
                }
        cout <<"edge from " <<l <<" to "<<k;
        cost[l][k]=-1;
        cost[k][l]=-1;
        visit++;
        int count=0;
        count1=0;
        for(i=1; i<=n; i++)
        {
            if(visited[i]==l)
                count++;
            if(visited[i]==k)
                count1++;
        }
        if(count==0)
            visited[++vst]=l;
        if(count1==0)
            visited[++vst]=k;
    }
}

int main()
{
    creategraph();
    kruskal();
    getch();
}

thinkerman 0 Newbie Poster · Answer 5 · 2012-09-23T21:30:36+00:00

    #include<iostream>
    #include<stdlib.h>
    using namespace std;
    int weight[20][20],visited[20],d[20],p[20];
    int v,e;

    void creategraph()
    {
        int i,j,a,b,w;
        cout<<"Enter number of vertices: ";
        cin>>v;
        cout<<"\nEnter number of edges: ";
        cin>>e;
        for(i=1;i<=v;i++)
            for(j=1;j<=v;j++)
                weight[i][j]=0;
        for(i=1;i<=v;i++)
        {
             p[i]=visited[i]=0;
             d[i]=32767;
        }
        for(i=1;i<=e;i++)
        {
          cout<<"\nEnter edge a, b and weight w: ";
          cin>>a>>b>>w;
          weight[a][b]=weight[b][a]=w;
        }
    }

    void kruskal()
    {
        int cost[10][10],i,j,k,n,c,visit,visited[10],l,v,count1,vst,p,dup1,dup2;
        for(k=0;k<e;k++)1;
        {
            cin >>i >>j >>c;
            cost[i][j]=c;
            cost[j][i]=c;
        }
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(cost[i][j]==0)
                    cost[i][j]=31999;
        visit=1;
        while(visit<n)
        {
            v=31999;
            for(i=0;i<n;i++)
                for(j=0;j<n;j++)
                    if(cost[i][j]!=31999 && cost[i][j]<v  && cost[i][j]!=-1)
                    {
                        int count =0;
                        for(p=0;p<n;p++)
                    {
                            if(visited[p]==i || visited[p]==j)
                                count++;
                    }
                    if(count >= 2)
                    {
                        for(p=0;p<n;p++)
                            if(cost[i][p]!=31999 && p!=j)
                                dup1=p;
                    for(p=0;p<n;p++)
                        if(cost[j][p]!=31999 && p!=i)
                            dup2=p;
                    if(cost[dup1][dup2]==-1)
                        continue;
                }
                l=i;
                k=j;
                v=cost[i][j];
            }
        cout <<"edge from " <<l <<" to "<<k;
        cost[l][k]=-1;
        cost[k][l]=-1;
        visit++;
        int count=0;
        count1=0;
        for(i=0;i<n;i++)
        {
            if(visited[i]==l)
                count++;
            if(visited[i]==k)
                count1++;
        } 
        if(count==0)
            visited[++vst]=l;
        if(count1==0)
            visited[++vst]=k;
        }
    }

    int main()
    {
        creategraph();
        kruskal();
    }

I get the following warning:
warning C4700: uninitialized local variable 'n' used line 39

thinkerman 0 Newbie Poster · Answer 6 · 2012-09-23T22:01:19+00:00

What should n be initialized to? Can it be zero? Where do I place the initialation in the program?

Bob 15 using namespace Bob Team Colleague · Answer 7 · 2012-09-23T22:06:32+00:00

What should n be initialized to? Can it be zero? Where do I place the initialation in the program?

It can be initialised to whatever valid value you wish, anywhere prior to first use (currently line 39). What was your intention when you wrote the loop? What purpose is it intended to serve?

WaltP 2,905 Posting Sage w/ dash of thyme Team Colleague · Answer 8 · 2012-09-24T01:15:49+00:00

What should n be initialized to? Can it be zero? Where do I place the initialation in the program?

If you don't know what n should be, why did you ise the statement
for(i=0;i<n;i++)? Using n implied you know what it is and why.

happyuk 0 Newbie Poster · Answer 9 · 2013-04-14T21:35:35+00:00

Hi

Please refer to these blog postings for C++ / MFC / Boost / C# implementations of Kruskal.

Let me know if you need help in using them

For your information, I found the following Wiki pages to be excellent sources of information in understanding the workings of Kruskal, Prim etc for finding minmal spanning trees:

http://en.wikipedia.org/wiki/Kruskal%27s_algorithm
http://en.wikipedia.org/wiki/Prim%27s_algorithm

Aiman_1 0 Newbie Poster · Answer 10 · 2017-05-23T03:48:18+00:00

sir, can u explian to me, why you set mincost=32767; ?