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.
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.
Download
No comments:
Post a Comment