GRAPH TRAVERSAL : BFS & DFS

 

GRAPH TRAVERSL:

   1]  BFS

   2] DFS

BFS:

//bfs

#include<stdio.h>

 #define maxsize 20

 typedef struct node

  {

     int data[maxsize];

     int front,end;

  }queue;

  int initq(queue *pq)

   {

      pq->front=pq->end=-1;

   }

  int isempty(queue *pq)

   {

      return (pq->end==pq->front);

   }

  void enqueue(queue *pq,int n)

   {

       pq->data[++pq->end]=n;

   }

  int dequeue(queue *pq)

   {

       return pq->data[++pq->front];

   }

  int bfs(int a[4][4],int n)

   {

     int w,v;

     int visited[25]={0};

     queue q;

     initq(&q);

     printf("\nBreadth First Search is:");

     v=0;            //starting vertex is 0

     visited[v]=1;

     enqueue(&q,v);

      while(!isempty(&q))

        {

          v=dequeue(&q);

          printf("v%d",v+1);

          for(w=0;w<n;w++)

             if( (a[v][w]==1) && (visited[w]==0) )

               {

                  enqueue(&q,w);

                  visited[w]=1;

               }

        }

   }

  int main()

   {

      int m[4][4]={{0,0,1,0},

                    {1,0,0,1},

                    {0,1,0,0},

                    {0,0,1,0}};

                 

        bfs(m,4);

   }

DFS:

 #include<stdio.h>

 int dfs(int m[4][4],int n,int v)

  {

      int w;

      static int visited[16]={0};

      visited[v]=1;

      printf("\tv%d",v+1);

       for(w=0;w<n;w++)

         {

          if((m[v][w]==1) && (visited[w]==0))

              dfs(m,n,w);

         }

  }        

 int main()

 {

    int m[4][4]={{0,0,0,1},

                 {0,0,1,0},

                 {0,0,0,1},

                 {1,1,0,0}};

    dfs(m,4,0);

 }

C