DEPTH FIRST SEARCH IN GRAPH

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

int a [10][10];

int visited[10],n;

void main()

{

            int i,j;

            void searchfrom(int);

            clrscr();

            printf("enter the no. of nodes\n");

            scanf("%d",&n);

            printf("enter the adjacency matrix\n");

for(i=1;i<=n;i++)

for(j=1;j<=n;j++)

scanf("%d",&a[i][j]);

for(i=1;i<=n;i++)

visited[i]=0;

printf("Depth First Path:");

for(i=1;i<=n;i++)

if(visited[i]==0)

searchfrom(i);

}

void searchfrom(int k)

{

            int i;

            printf("%d\t",k);

            visited[k]=1;

            for(i=1;i<=n;i++)

            if(visited[i]==0)

            searchfrom(i);

            return;

}

output:

enter the no. of nodes

3

enter the adjacency matrix

1 0 0

0 1 0

0 0 1

Depth First Path:1      2       3

breadth first search in graph

#include<stdio.h>

#include<conio.h>

int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;

void bfs(int v)

{

 for(i=1;i<=n;i++)

  if(a[v][i] && !visited[i])

            q[++r]=i;

 if(f<=r)

 {

  visited[q[f]]=1;

  bfs(q[f++]);

 }

}

void main()

{

 int v;

 clrscr();

 printf("\nEnter the number of vertices:");

 scanf("%d",&n);

 for(i=1;i<=n;i++)

 {

  q[i]=0;

  visited[i]=0;

 }

 printf("\n Enter graph data in matrix form:\n");

 for(i=1;i<=n;i++)

  for(j=1;j<=n;j++)

            scanf("%d",&a[i][j]);

 printf("\n Enter the starting vertex:");

 scanf("%d",&v);

 bfs(v);

 printf("\n The node which are reachable are:\n");

 for(i=1;i<=n;i++)

  if(visited[i])

            printf("%d\t",i);

  else

            printf("\n Bfs is not possible");

 getch();

}

output:

Enter the number of vertices:3

 Enter graph data in matrix form:

1

2

3

4

5

6

7

8

9

Enter the starting vertex:3

 The node which are reachable are:

1       2       3