If each vertex in a graph is to be traversed by a tree-based algorithm (such as DFS or BFS), then the algorithm must be called at least once for each connected component of the graph. This is easily accomplished by iterating through all the vertices of the graph, performing the algorithm on each vertex that is still unvisited when examined.

1.  Breadth First Search

2. Depth First Search

1. Breadth First Search

A breadth-first search (BFS) is another technique for traversing a finite graph. BFS visits the sibling vertices before visiting the child vertices, and a queue is used in the search process. This algorithm is often used to find the shortest path from one vertex to another.

Pseudocode

• Input: A graph G and a vertex v of G.
• Output: The closest vertex to v satisfying some conditions, or null if no such vertex exists

procedure BFS(G, v):
   create a queue Q   
   enqueue v onto Q
   mark v
   while Q is not empty do
       w ← Q.dequeue()
       if w is what we are looking for then
           return w
       for all edges e in G.adjacentEdges(w) do
           x ← G.adjacentVertex(w, e)
           if x is not marked then
              mark x
              enqueue x onto Q
    return null

Sample Program:

/* C program to implement BFS(breadth-first search) algorithm */

#include<stdio.h>
#include<stdlib.h>

int q[20],front=-1,rear=-1,a[20][20],visited[20];

int delete();
void add(int item);
void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();

int main()
{
	int n,i,s,choice,j;
	char ch;
	printf("\nENTER THE NUMBER VERTICES : ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf("\nENTER 1 IF (%d, %d) HAS A NODE, ELSE 0 : ",i,j);
			scanf("%d",&a[i][j]);
		}
	}

	printf("THE ADJACENCY MATRIX IS\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf(" %d",a[i][j]);
		}
		printf("\n");
	}

	do
	{
		for(i=1;i<=n;i++)
			visited[i]=0;
	
		printf("\nMENU");
		printf("\n1.B.F.S");
		printf("\n0.Exit");
		printf("\nENTER YOUR CHOICE :");
		scanf("%d",&choice);
		printf("\nENTER THE SOURCE VERTEX :");
		scanf("%d",&s);

		switch(choice)
		{
			case 1:
				bfs(s,n);
				break;
			case 0:
				exit(0);
				break;
			default:
				printf("\nWrong Choice ");
				break;
		}
		printf("\nDO U WANT TO CONTINUE(Y/N) ? : ");
		scanf("%s",&ch);
	}while((ch=='y')||(ch=='Y'));
	return(0);
}


//BFS(breadth-first search) code
void bfs(int s,int n)
{
	int p,i;
	add(s);
	visited[s]=1;
	p=delete();
	if(p!=0)
		printf(" %d",p);
	while(p!=0)
	{
		for(i=1;i<=n;i++)
		{
			if((a[p][i]!=0)&&(visited[i]==0))
			{
				add(i);
				visited[i]=1;
			}
		}
		p=delete();
		if(p!=0)
			printf(" %d ",p);
	}
	for(i=1;i<=n;i++)
		if(visited[i]==0)
	bfs(i,n);
}


void add(int item)
{
	if(rear==19)
		printf("QUEUE FULL");
	else
	{
		if(rear==-1)
		{
			q[++rear]=item;
			front++;
		}
		else
			q[++rear]=item;
	}
}


int delete()
{
	int k;
	if((front>rear)||(front==-1))
		return(0);
	else
	{
		k=q[front++];
		return(k);
	}
}

/*
Output
harish@harish-Veriton-M200-H110:~/harish/ds/DSF$ gcc bfs.c
harish@harish-Veriton-M200-H110:~/harish/ds/DSF$ ./a.out

ENTER THE NUMBER VERTICES : 3

ENTER 1 IF (1, 1) HAS A NODE, ELSE 0 : 0

ENTER 1 IF (1, 2) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (1, 3) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (2, 1) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (2, 2) HAS A NODE, ELSE 0 : 0

ENTER 1 IF (2, 3) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (3, 1) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (3, 2) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (3, 3) HAS A NODE, ELSE 0 : 0
THE ADJACENCY MATRIX IS
 0 1 1
 1 0 1
 1 1 0

MENU
1.B.F.S
0.Exit
ENTER YOUR CHOICE :1

ENTER THE SOURCE VERTEX :1
 1 2  3 
DO U WANT TO CONTINUE(Y/N) ? : n
harish@harish-Veriton-M200-H110:~/harish/ds/DSF$ 
*/

2. Depth-First-Search

A depth-first search (DFS) is an algorithm for traversing a finite graph. DFS visits the child vertices before visiting the sibling vertices; that is, it traverses the depth of any particular path before exploring its breadth. A stack (often the program's call stack via recursion) is generally used when implementing the algorithm.

The algorithm begins with a chosen "root" vertex; it then iteratively transitions from the current vertex to an adjacent, unvisited vertex, until it can no longer find an unexplored vertex to transition to from its current location. The algorithm then backtracks along previously visited vertices, until it finds a vertex connected to yet more uncharted territory. It will then proceed down the new path as it had before, backtracking as it encounters dead-ends, and ending only when the algorithm has backtracked past the original "root" vertex from the very first step.

DFS is the basis for many graph-related algorithms, including topological sorts and planarity testing.

Pseudocode

• Input: A graph G and a vertex v of G.
• Output: A labeling of the edges in the connected component of v as discovery edges and back edges.

procedure DFS(G, v):
     label v as explored
     for all edges e in G.incidentEdges(v) do
         if edge e is unexplored then
             w ← G.adjacentVertex(v, e)
             if vertex w is unexplored then
                 label e as a discovered edge
                 recursively call DFS(G, w)
             else
               label e as a back edge

Sample Program:

/* C program to implement DFS(depth-first search) algorithm */

#include<stdio.h>
#include<stdlib.h>

int top=-1,a[20][20],visited[20],stack[20];

int delete();
void add(int item);
void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();

int main()
{
	int n,i,s,choice,j;
	char ch;
	printf("\nENTER THE NUMBER VERTICES : ");
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf("\nENTER 1 IF (%d, %d) HAS A NODE, ELSE 0 : ",i,j);
			scanf("%d",&a[i][j]);
		}
	}

	printf("THE ADJACENCY MATRIX IS\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			printf(" %d",a[i][j]);
		}
		printf("\n");
	}
	do
	{
		for(i=1;i<=n;i++)
			visited[i]=0;
	
		printf("\nMENU");
		printf("\n1.D.F.S");
		printf("\n0.Exit");
		printf("\nENTER YOUR CHOICE :");
		scanf("%d",&choice);
		printf("\nENTER THE SOURCE VERTEX :");
		scanf("%d",&s);

		switch(choice)
		{
			case 1:
				dfs(s,n);
				break;
			case 0:
				exit(0);
				break;
			default:
				printf("\nWrong Choice ");
				break;
		}
		printf("\nDO U WANT TO CONTINUE(Y/N) ? : ");
		scanf("%s",&ch);
	}while((ch=='y')||(ch=='Y'));
	return(0);
}


//DFS(depth-first search) code
void dfs(int s,int n)
{
	int i,k;
	push(s);
	visited[s]=1;
	k=pop();
	if(k!=0)
		printf(" %d ",k);
	while(k!=0)
	{
		for(i=1;i<=n;i++)
		{
			if((a[k][i]!=0)&&(visited[i]==0))
			{
				push(i);
				visited[i]=1;
			}
		}
		k=pop();
		if(k!=0)
			printf(" %d ",k);
	}
	for(i=1;i<=n;i++)
		if(visited[i]==0)
	dfs(i,n);
}

void push(int item)
{
	if(top==19)
		printf("Stack overflow ");
	else
		stack[++top]=item;
}

int pop()
{
	int k;
	if(top==-1)
		return(0);
	else
	{
		k=stack[top--];
		return(k);
	}
}

/*
Output
harish@harish-Veriton-M200-H110:~/harish/ds/DSF$ gcc dfs.c
harish@harish-Veriton-M200-H110:~/harish/ds/DSF$ ./a.out

ENTER THE NUMBER VERTICES : 3

ENTER 1 IF (1, 1) HAS A NODE, ELSE 0 : 0

ENTER 1 IF (1, 2) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (1, 3) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (2, 1) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (2, 2) HAS A NODE, ELSE 0 : 0

ENTER 1 IF (2, 3) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (3, 1) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (3, 2) HAS A NODE, ELSE 0 : 1

ENTER 1 IF (3, 3) HAS A NODE, ELSE 0 : 0
THE ADJACENCY MATRIX IS
 0 1 1
 1 0 1
 1 1 0

MENU
1.D.F.S
0.Exit
ENTER YOUR CHOICE :1

ENTER THE SOURCE VERTEX :1
 1  3  2 
DO U WANT TO CONTINUE(Y/N) ? : n
harish@harish-Veriton-M200-H110:~/harish/ds/DSF$ 
*/