Graph Traversal

 /* Program for traversing a graph through BFS and DFS */  
 #include<iostream.h>  
 #include<stdlib.h>  
 #include<conio.h>  
 #define MAX 20  
 int create_graph();  
 int dfs_rec(int);  
 int display();  
 int dfs(int);  
 int bfs(int);  
 int adj_nodes(int);  
 int components();  
 typedef enum boolean{false,true} bool;  
 int adj[MAX][MAX];  
 bool visited[MAX];  
 int n;  /* Denotes number of nodes in the graph */  
 void main()  
 {  
      int i,v,choice;  
      clrscr();  
      create_graph();  
      while(1)  
      {  
           clrscr();  
           cout<<endl;  
           cout<<"1. Adjacency matrix"<<endl;  
           cout<<"2. Depth First Search using stack"<<endl;  
           cout<<"3. Depth First Search through recursion"<<endl;  
           cout<<"4. Breadth First Search"<<endl;  
           cout<<"5. Adjacent vertices"<<endl;  
           cout<<"6. Components"<<endl;  
           cout<<"7. Exit"<<endl;  
           cout<<"\n\nEnter your choice : ";  
           cin>>choice;  
           switch(choice)  
           {  
            case 1:  
                cout<<"\n\n\nAdjacency Matrix\n"<<endl;  
                display();  
                break;  
            case 2:  
                cout<<"\n\n\nEnter starting node for Depth First Search : "<<endl;  
                cin>>v;  
                for(i=1;i<=n;i++)  
                     visited[i]=false;  
                dfs(v);  
                break;  
            case 3:  
                cout<<"\n\n\nEnter starting node for Depth First Search : ";  
                cin>>v;  
                for(i=1;i<=n;i++)  
                     visited[i]=false;  
                dfs_rec(v);  
                break;  
            case 4:  
                cout<<"\n\n\nEnter starting node for Breadth First Search : ";  
                cin>>v;  
                for(i=1;i<=n;i++)  
                     visited[i]=false;  
                bfs(v);  
                break;  
            case 5:  
                cout<<"\n\n\nEnter node to find adjacent vertices : ";  
                cin>>v;  
                cout<<"\n\nAdjacent Vertices are : ";  
                adj_nodes(v);  
                break;  
            case 6:  
                components();  
                break;  
            case 7:  
                exit(1);  
            default:  
                cout<<"\n\n\n\t\t\tWrong choice"<<endl;  
                break;  
            }/*End of switch*/  
            getch();  
      }/*End of while*/  
 }/*End of main()*/  
 create_graph()  
 {  
      int i,max_edges,origin,destin;  
      cout<<"Enter number of nodes : ";  
      cin>>n;  
      max_edges=n*(n-1);  
      for(i=1;i<=max_edges;i++)  
      {  
           cout<<"Enter edge %d( 0 0 to quit ) : "<<i<<endl;  
           cin>>origin>>destin;  
           if((origin==0) && (destin==0))  
                break;  
           if( origin > n || destin > n || origin<=0 || destin<=0)  
           {  
                cout<<"Invalid edge!\n";  
                i--;  
           }  
           else  
           {  
                adj[origin][destin]=1;  
                adj[destin][origin]=1;  
           }  
      }/*End of for*/  
 }/*End of create_graph()*/  
 display()  
 {  
      int i,j;  
      for(i=1;i<=n;i++)  
      {  
           for(j=1;j<=n;j++)  
                cout<<adj[i][j]<<'\t';  
           cout<<endl;  
      }  
 }/*End of display()*/  
 dfs_rec(int v)  
 {  
      int i;  
      visited[v]=true;  
      cout<<v<<'\t';  
      for(i=1;i<=n;i++)  
           if(adj[v][i]==1 && visited[i]==false)  
                dfs_rec(i);  
 }/*End of dfs_rec()*/  
 dfs(int v)  
 {  
      int i,stack[MAX],top=-1,pop_v,j,t;  
      int ch;  
      top++;  
      stack[top]=v;  
      while (top>=0)  
      {  
           pop_v=stack[top];  
           top--;           /*pop from stack*/  
           if( visited[pop_v]==false)  
           {  
                cout<<pop_v<<'\t';  
                visited[pop_v]=true;  
           }  
           else  
                continue;  
           for(i=n;i>=1;i--)  
           {  
                if( adj[pop_v][i]==1 && visited[i]==false)  
                {  
                     top++;  /* push all unvisited neighbours of pop_v */  
                     stack[top]=i;  
                }/*End of if*/  
           }/*End of for*/  
      }/*End of while*/  
 }/*End of dfs()*/  
 bfs(int v)  
 {  
      int i,front,rear;  
      int que[20];  
      front=rear= -1;  
      cout<<v<<'\t';  
      visited[v]=true;  
      rear++;  
      front++;  
      que[rear]=v;  
      while(front<=rear)  
      {  
           v=que[front];      /* delete from queue */  
           front++;  
           for(i=1;i<=n;i++)  
           {  
                /* Check for adjacent unvisited nodes */  
                if( adj[v][i]==1 && visited[i]==false)  
                {  
                     cout<<i<<'\t';  
                     visited[i]=true;  
                     rear++;  
                     que[rear]=i;  
                 }  
           }  
      }/*End of while*/  
 }/*End of bfs()*/  
 adj_nodes(int v)  
 {  
      int i;  
      for(i=1;i<=n;i++)  
      if(adj[v][i]==1)  
           cout<<i<<endl;  
 }/*End of adj_nodes()*/  
 components()  
 {  
      int i;  
      for(i=1;i<=n;i++)  
           visited[i]=false;  
      for(i=1;i<=n;i++)  
      {  
           if(visited[i]==false)  
                dfs_rec(i);  
      }  
      cout<<endl;  
 }/*End of components()*/