Data Structures Depth,Breath search C Program

This Program is for Depth First, Breath First Search in C program, and is a part of Mumbai University MCA Colleges Data Structures in C program MCA Sem 2

#include<stdio.h>
#include<conio.h>
#define MAX 20

typedef enum boolean{false,true} bool;
int adj[MAX][MAX];
bool visited[MAX];
int n;
main()
{
          int i,v,choice;
          clrscr();
printf("====================== TRAVERSAL IN GRAPH =====================\n");
          create_graph();
          while(1)
          {
                   printf("\n");
                   printf("\n1. Adjacency matrix\n");
                   printf("\n2. Depth First Search using stack\n");
                   printf("\n3. Depth First Search through recursion\n");
                   printf("\n4. Breadth First Search\n");
                   printf("\n5. Adjacent vertices\n");
                   printf("\n6. Components\n");
                   printf("\n7. Exit\n");
                   printf("\nEnter your choice : ");
                   scanf("%d",&choice);

                   switch(choice)
                   {
                    case 1:
                             printf("\nAdjacency Matrix\n");
                             display();
                             break;
                    case 2:
                             printf("\nEnter starting node for Depth First Search : ");
                             scanf("%d",&v);
                             for(i=1;i<=n;i++)
                                      visited[i]=false;
                             dfs(v);
                             break;
                    case 3:
                             printf("\nEnter starting node for Depth First Search : ");
                             scanf("%d",&v);
                             for(i=1;i<=n;i++)
                                      visited[i]=false;
                             dfs_rec(v);
                             break;
                    case 4:
                             printf("\nEnter starting node for Breadth First Search : ");
                             scanf("%d", &v);
                             for(i=1;i<=n;i++)
                                      visited[i]=false;
                             bfs(v);
                             break;
                    case 5:
                             printf("\nEnter node to find adjacent vertices : ");
                             scanf("%d", &v);
                             printf("Adjacent Vertices are : ");
                             adj_nodes(v);
                             break;
                    case 6:
                             components();
                             break;
                    case 7:
                             exit(1);
                    default:
                             printf("Wrong choice\n");
                             break;
                    }
          }
          getch();
}

create_graph()
{
          int i,max_edges,origin,destin;

          printf("\nEnter number of nodes : ");
          scanf("%d",&n);
          max_edges=n*(n-1);

          for(i=1;i<=max_edges;i++)
          {
                   printf("\nEnter edge %d( 0 0 to quit ) : ",i);
                   scanf("%d %d",&origin,&destin);

                   if((origin==0) && (destin==0))
                             break;

                   if( origin > n || destin > n || origin<=0 || destin<=0)
                   {
                             printf("Invalid edge!\n");
                             i--;
                   }
                   else
                   {
                             adj[origin][destin]=1;
                   }
          }
}

display()
{
          int i,j;
          for(i=1;i<=n;i++)
          {
                   for(j=1;j<=n;j++)
                             printf("%4d",adj[i][j]);
                   printf("\n");
          }
}

dfs_rec(int v)
{
          int i;
          visited[v]=true;
          printf("%d ",v);
          for(i=1;i<=n;i++)
                   if(adj[v][i]==1 && visited[i]==false)
                             dfs_rec(i);
}

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--;
                   if( visited[pop_v]==false)
                   {
                             printf("%d ",pop_v);
                             visited[pop_v]=true;
                   }
                   else
                             continue;

                   for(i=n;i>=1;i--)
                   {
                             if( adj[pop_v][i]==1 && visited[i]==false)
                             {
                                      top++;
                                      stack[top]=i;
                             }
                   }
          }
}

bfs(int v)
{
          int i,front,rear;
          int que[20];
          front=rear= -1;

          printf("%d ",v);
          visited[v]=true;
          rear++;
          front++;
          que[rear]=v;

          while(front<=rear)
          {
                   v=que[front];
                   front++;
                   for(i=1;i<=n;i++)
                   {

                             if( adj[v][i]==1 && visited[i]==false)
                             {
                                      printf("%d ",i);
                                      visited[i]=true;
                                      rear++;
                                      que[rear]=i;
                              }
                   }
          }
}

adj_nodes(int v)
{
          int i;
          for(i=1;i<=n;i++)
          if(adj[v][i]==1)
                   printf("%d ",i);
          printf("\n");
}

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);
          }
          printf("\n");
}

Hope this Program is useful to you in some sense or other. Keep on following this blog for more Mumbai University MCA College Programs. Happy Programming and Studying.

No comments:

Post a Comment