DFS In C Program

Ram Pothuraju
#include < stdio.h>
#include < conio.h>
#define MAX 20
#define TRUE 1
#define FALSE 0


int g[MAX][MAX];
int v[MAX];
int n;

void create();
void DFS();

void main()
{
 int i,j;
 char ans;
 clrscr();
 printf("\n----------------------------------------------------");
 printf("\n          DEPTH FIRST SEARCH");
 printf("\n----------------------------------------------------");
 create();
 getch();
 
 printf("\n Adjacency Matrix for the graph is:");
 printf("\n----------------------------------------------------");
 for(i=0;i < n;i++)
 {
  printf("\n");
  for(j=0;j < n;j++)
   printf("%4d",g[i][j]);
 }
 getch();

 do
 {
  for(i=0;i < n;i++)
   v[i]=FALSE;

 
  printf("\n Enter Vertex from which you Want to traverse:");
  scanf("%d",&i);
 
  if(i>=MAX)
   printf("\n Invalid Vertex");
  else
  {
   printf("\n The Depth First Search of the Graph is:");
   printf("\n----------------------------------------------------\n");
   DFS(i);
   printf("\n----------------------------------------------------\n");
  }
  printf("\n Dou want to Traverse By other node?");
  ans=getch();
 }while(ans=='y' || ans=='Y');
}

void create()
{
 int ch,i,j,flag;
 char ans='y';
 
 printf("\n This section is for Creating a Graph.");
 
 for(i=0;i < n;i++)
  for(j=0;j < n;j++)
   g[i][j]=FALSE;
   
 printf("\n Enter number of nodes:");
 scanf("%d",&n);
 
 printf("\n Enter the vertices no. starting from 0");


 do{
  printf("\n Enter the vertices v1 & v2:");
  scanf("%d %d",&i,&j);
 
  if(i>=n && j>=n)
  {
   printf("\n Invali Vertex value.");
  }
  else
  {
   g[i][j]=TRUE;
   g[j][i]=TRUE;
  }
  printf("\n Add more Edges?(y/n)");
  ans=getch();
 }while(ans=='y' || ans=='Y');
}

void DFS(int i)
{
 int j;
 printf("%d-->",i);
 v[i]=TRUE;
 
 for(j=0;j < MAX;j++)
  if(g[i][j]==TRUE && v[j]==FALSE)
   DFS(j);
}

OUTPUT


----------------------------------------------------
          DEPTH FIRST SEARCH
----------------------------------------------------
 This section is for Creating a Graph.
 Enter number of nodes:4

 Enter the vertices no. starting from 0
 Enter the vertices v1 & v2:0 1

 Add more Edges?(y/n)
 Enter the vertices v1 & v2:0 2

 Add more Edges?(y/n)
 Enter the vertices v1 & v2:1 3

 Add more Edges?(y/n)
 Enter the vertices v1 & v2:2 3

 Add more Edges?(y/n)
 Adjacency Matrix for the graph is:
----------------------------------------------------
   0   1   1   0
   1   0   0   1
   1   0   0   1
   0   1   1   0
Enter Vertex from which you Want to traverse:0

 The Depth First Search of the Graph is:
----------------------------------------------------
0-->1-->3-->2-->
----------------------------------------------------

 Dou want to Traverse By other node?

Post a Comment

0Comments

Post a Comment (0)