We are hiring content writers to work from home

Resources » Articles/Knowledge Sharing » Computer & Technology

# C Program for traversing a graph through BFS and DFS

 Posted Date: 24-Mar-2008 Last Updated: 24-Mar-2008 Category: Computer & Technology Author: ashish singh Member Level: Gold Points: 5

/* Program for traversing a graph through BFS and DFS */
#include
#define MAX 20

typedef enum boolean{false,true} bool;
bool visited[MAX];
int n; /* Denotes number of nodes in the graph */
main()
{
int i,v,choice;

create_graph();
while(1)
{
printf("\n");
printf("2. Depth First Search using stack\n");
printf("3. Depth First Search through recursion\n");
printf("4. Breadth First Search\n");
printf("6. Components\n");
printf("7. Exit\n");
printf("Enter your choice : ");
scanf("%d",&choice);

switch(choice)
{
case 1:
display();
break;
case 2:
printf("Enter starting node for Depth First Search : ");
scanf("%d",&v);
for(i=1;i<=n;i++)
visited[i]=false;
dfs(v);
break;
case 3:
printf("Enter 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("Enter starting node for Breadth First Search : ");
scanf("%d", &v);
for(i=1;i<=n;i++)
visited[i]=false;
bfs(v);
break;
case 5:
printf("Enter node to find adjacent vertices : ");
scanf("%d", &v);
printf("Adjacent Vertices are : ");
break;
case 6:
components();
break;
case 7:
exit(1);
default:
printf("Wrong choice\n");
break;
}/*End of switch*/
}/*End of while*/
}/*End of main()*/

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

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

for(i=1;i<=max_edges;i++)
{
printf("Enter 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
{
}
}/*End of for*/
}/*End of create_graph()*/

display()
{
int i,j;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf("\n");
}
}/*End of display()*/

dfs_rec(int v)
{
int i;
visited[v]=true;
printf("%d ",v);
for(i=1;i<=n;i++)
dfs_rec(i);
}/*End of dfs_rec()*/

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--; /*pop from stack*/
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++; /* push all unvisited neighbours of pop_v */
stack[top]=i;
}/*End of if*/
}/*End of for*/
}/*End of while*/
}/*End of dfs()*/

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]; /* delete from queue */
front++;
for(i=1;i<=n;i++)
{
/* Check for adjacent unvisited nodes */
if( adj[v][i]==1 && visited[i]==false)
{
printf("%d ",i);
visited[i]=true;
rear++;
que[rear]=i;
}
}
}/*End of while*/
}/*End of bfs()*/

{
int i;
for(i=1;i<=n;i++)
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");
}/*End of components()*/

Did you like this resource? Share it with your friends and show your love!

Responses to "C Program for traversing a graph through BFS and DFS"

No responses found. Be the first to respond...

Feedbacks

## Post Comment:

• Do not include your name, "with regards" etc in the comment. Write detailed comment, relevant to the topic.
• No HTML formatting and links to other web sites are allowed.
• This is a strictly moderated site. Absolutely no spam allowed.
•  Name: Sign In to fill automatically. Email: (Will not be published, but required to validate comment) Type the numbers and letters shown on the left.

 Next Resource: C Program for topological sorting Previous Resource: C Program to find path matrix by Warshall's algorithm Return to Resources Post New Resource Category: Computer & Technology

Post resources and earn money!

More Resources
 Popular Tags Tag posting guidelines Search Tags

### Subscribe to Email

• Get Jobs by Email
• Forum posts by Email
• Articles by Email
• Awards & Gifts
Active Members
TodayLast 7 Days
more...