connected components of an undirected graph

[Himani Joshi]

i have written a program to find the connected components of an undirected graph with the concept of depth-first search..but there seems to be some problem as the program keeps hanging and then does not respond..can anyone help debugging it? its urgent. thanx in advance!

#include <iostream.h>
struct node
{
int vertex_no;
int adj[20];
};
node V[20];
int v;
char color[20];

void dfs_visit(int i)
{
color[i]='g';
for (int j=0; V[i].adj[j]!=0;j++)
{
if(color[j]=='w')
dfs_visit(V[i].adj[j]);
}
color[i]='b';
}
int main()
{
for(int i=0;i<20;i++)
for(int j=0;j<20;j++)
V[i].adj[j]=0;
cout<<"Enter the number of vertices in the graph : ";
cin>>v;
cout<<"Graph contains following vertices : ";
for(int i=1;i<=v;i++)
{
cout<<i;
if(i<v)
cout<<", ";
}
cout<<"\n";
for(int i=1;i<=v;i++)
{
cout<<"\nEnter adjacents of vertex "<<i<<" one by one. \n( Press 0 when no more adjacents have to be added )\n";
int n=100;
int mark=0,j=0;
while(n!=0)
{
cin>>n;
if((n>v)||(n==i))
{
cout<<"Please enter a valid vertex";
continue;
}
V[i].adj[mark]=n;
mark++;
}
}
cout<<"The undirected graph you entered is as follows in adjanceny list representation:\n";
for(int i=1;i<=v;i++)
{
cout<<i;
for(int j=0;j<20;j++)
{
if(V[i].adj[j]==0)
break;
cout<<"-->"<<V[i].adj[j];
}
cout<<"\n";
}

//Using DFS to find out the connected components of the graph

for(int i=0;i<=v;i++)
{
color[i]='w';
}

void dfs_visit(int i);

for(int i=1;i<=v;i++)
{
if(i>1)
{
cout<<"Connected component "<<i-1<<" :";
for(int i=1;i<=v;i++)
{
if(color[v]='b')
cout<<i<<" ";
color[v]='z';
}
cout<<"\n";
}
if(color[i]=='w')
dfs_visit(i);
}


cout<<"\n";
system("pause");
}

[histrungalot]

I'm trying to work with what you have because I don't want to change it too much.
I'm not sure if this is the best way to do things but check this out.

#include <iostream>

using namespace std;
struct node
{
   int vertex_no;
   int adj[20]; 
};
node V[20];
int v;
char color[20];

void dfs_visit(int i)
{
   color[i]='g';
//   cout << "Setting " << i << " to gray" << endl;
   for (int j=0; V[i].adj[j]!=0;j++)
   {
      //cout << "Checking " << V[i].adj[j] << " color" << endl;
      if(color[V[i].adj[j]]=='w')
          dfs_visit(V[i].adj[j]);
   }
   color[i]='b';
   //cout << "Setting " << i << " to BLACK" << endl;
}




int main()
{
   for(int i=0;i<20;i++)
      for(int j=0;j<20;j++)
         V[i].adj[j]=0;
      cout<<"Enter the number of vertices in the graph : ";
      cin>>v;
      cout<<"Graph contains following vertices : ";
      for(int i=1;i<=v;i++)
      { 
         cout<<i;
         if(i<v)
            cout<<", ";
      }
      cout<< endl;
      for(int i=1;i<=v;i++)
      {
         cout<<"\nEnter adjacents of vertex "<<i<<" one by one. \n( Press 0 when no more adjacents have to be added )" << endl;
         int n=100;
         int mark=0,j=0;
         while(n!=0)
         {
            cin>>n;
            if((n>v)||(n==i))
            {
               cout<<"Please enter a valid vertex";
               continue;
            }
            V[i].adj[mark]=n;
            mark++;
         } 
      }
      cout<<"The undirected graph you entered is as follows in adjanceny list representation:" << endl;
      for(int i=1;i<=v;i++)
      {
          cout<<i;
          for(int j=0;j<20;j++)
          {
             if(V[i].adj[j]==0)
              break;
             cout<<"-->"<<V[i].adj[j];
          }
          cout<<"\n";
      }

      //Using DFS to find out the connected components of the graph

      for(int i=1;i<=v;i++)
      {
          color[i]='w';
      }
         
     for(int i=1;i<=v;i++)
     {
        if(i>1)
        {
            cout<<"Connected component "<<i-1<<" :";
            for(int i=1;i<=v;i++)
            {
               if(color[i]=='b'){
                  cout<<i<<" ";
                  color[i]='z';
               }
            }
            cout<<"\n";
        }
        if(color[i]=='w')
           dfs_visit(i);
    }

}

./a.out
Enter the number of vertices in the graph : 5
Graph contains following vertices : 1, 2, 3, 4, 5

Enter adjacents of vertex 1 one by one. 
( Press 0 when no more adjacents have to be added )
2
3
0

Enter adjacents of vertex 2 one by one. 
( Press 0 when no more adjacents have to be added )
1
0

Enter adjacents of vertex 3 one by one. 
( Press 0 when no more adjacents have to be added )
1
0

Enter adjacents of vertex 4 one by one. 
( Press 0 when no more adjacents have to be added )
5
0

Enter adjacents of vertex 5 one by one. 
( Press 0 when no more adjacents have to be added )
4
0
The undirected graph you entered is as follows in adjanceny list representation:
1-->2-->3
2-->1
3-->1
4-->5
5-->4
Connected component 1 :1 2 3 
Connected component 2 :
Connected component 3 :
Connected component 4 :4 5 

Notes: Don't use 1 as the base index for your arrays (didn't fix that). Remember to use '==' and not '=' when checking for equality in if statements (had to fix that). Add print statements to your code to see what is going on if you don't have a debugger (added some but commented them out). Do a difference between mine and your to see what I changed.

[Himani Joshi]

thanx..this helped :)
made some changes to the program and now its working correctly :

#include <iostream.h>
struct node
{
int vertex_no;
int adj[20];
};
node V[20];
int v;
char color[20];

void dfs_visit(int i)
{
color[i]='g';
for (int j=0; V[i].adj[j]!=0;j++)
{
if(color[V[i].adj[j]]=='w')
dfs_visit(V[i].adj[j]);
}
color[i]='b';
}
int main()
{
cout<<"Enter the number of vertices in the graph : ";
cin>>v;
cout<<"Graph contains following vertices : ";
for(int i=1;i<=v;i++)
{
cout<<i;
if(i<v)
cout<<", ";
}
cout<<"\n";
for(int i=1;i<=v;i++)
{
cout<<"\nEnter adjacents of vertex "<<i<<" one by one. \n( Press 0 when no more adjacents have to be added )\n";
int n=100;
int mark=0,j=0;
while(n!=0)
{
cin>>n;
if((n>v)||(n==i))
{
cout<<"Please enter a valid vertex";
continue;
}
V[i].adj[mark]=n;
mark++;
}
}
cout<<"The undirected graph you entered is as follows in adjanceny list representation:\n";
for(int i=1;i<=v;i++)
{
cout<<i;
for(int j=0;j<20;j++)
{
if(V[i].adj[j]==0)
break;
cout<<"-->"<<V[i].adj[j];
}
cout<<"\n";
}

//Using DFS to find out the connected components of the graph

for(int i=0;i<=v;i++)
{
color[i]='w';
}

int j = 1;
for(int i=1;i<=v;i++)
{
if(color[i]=='w')
dfs_visit(i);
for(int k=1;k<=v;k++)
{
if(color[k]=='b')
{
cout<<"Connected component "<<j<<" :";
while(k<=v)
{ if(color[k] =='b'){
cout<<k<<" ";
color[k]='z';}
k++;
}
cout<<"\n";
j++;
}
}


}


cout<<"\n";
system("pause");
}