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.

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.

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?

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 4 Years Ago by Ancient Dragon

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.

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();
}
    #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

Edited 4 Years Ago by thinkerman

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.

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

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?

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.

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

  1. http://www.technical-recipes.c...
  2. http://www.technical-recipes.c...
  3. http://www.technical-recipes.c...

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

This article has been dead for over six months. Start a new discussion instead.