Nov 29, 20224 min read

Breadth First Search and Depth First Search

Breadth-First Search

Breadth-first search is a graph traversal algorithm that starts traversing the graph from the root node and explores all the neighboring nodes. Then, it selects the nearest node and explores all the unexplored nodes. While using BFS for traversal, any node in the graph can be considered as the root node.

BFS is the most used approach to traverse the graph. It is a recursive algorithm to search all the vertices of a tree or graph.

Algorithm:

STEP 1: SET STATUS = 1 (ready state) for each node in G

STEP 2: Enqueue the starting node A and set its STATUS = 2 (waiting state)

STEP 3: Repeat Steps 4 and 5 until QUEUE is empty

STEP 4: Dequeue a node N. Process it and set its STATUS = 3 (processed state).

STEP 5: Enqueue all the neighbors of N that are in the ready state (whose STATUS = 1) and set

their STATUS = 2. (waiting state)

[END OF LOOP]

STEP 6: Exit

How it Works?

Below we have a directed graph having 7 vertices.

Adjacency List:

A: B, D

B: C, F

C: E, G

D: F

E: B, F

F: A

G: E

Step 1 - First, add A to queue1 and NULL to queue2.

QUEUE1 = {A}    
QUEUE2 = {NULL}

Step 2 - Now, delete node A from queue1 and add it into queue2. Insert all neighbors of node A to queue1.

QUEUE1 = {B, D}    
QUEUE2 = {A}

Step 3 - Now, delete node B from queue1 and add it into queue2. Insert all neighbors of node B to queue1.

QUEUE1 = {D, C, F}    
QUEUE2 = {A, B}

Step 4 - Now, delete node D from queue1 and add it into queue2. Insert all neighbors of node D to queue1. The only neighbor of Node D is F since it is already inserted, so it will not be inserted again.

QUEUE1 = {C, F}    
QUEUE2 = {A, B, D}

Step 5 - Delete node C from queue1 and add it into queue2. Insert all neighbors of node C to queue1.

QUEUE1 = {F, E, G}    
QUEUE2 = {A, B, D, C}

Step 6 - Delete node F from queue1 and add it into queue2. Insert all neighbors of node F to queue1. Since all the neighbors of node F are already present, we will not insert them again.

QUEUE1 = {E, G}    
QUEUE2 = {A, B, D, C, F}

Step 7 - Delete node E from queue1. Since all of its neighbors have already been added, so we will not insert them again. Now, all the nodes are visited, and the target node E is encountered into queue2.

QUEUE1 = {G}    
QUEUE2 = {A, B, D, C, F, E}

Depth-First Search

DFS is a recursive algorithm to search all the vertices of a tree data structure or a graph. The depth-first search (DFS) algorithm starts with the initial node of graph G and goes deeper until we find the goal node or the node with no children.

Algorithm:

STEP 1: SET STATUS = 1 (ready state) for each node in G

STEP 2: Push the starting node A on the stack and set its STATUS = 2 (waiting state)

STEP 3: Repeat Steps 4 and 5 until STACK is empty

STEP 4: Pop the top node N. Process it and set its STATUS = 3 (processed state)

STEP 5: Push on the stack all the neighbors of N that are in the ready state (whose STATUS = 1) and set their STATUS = 2 (waiting state)

[END OF LOOP]

STEP 6: EXIT

How it Works:

Adjacency Lists:

A: B, D

B: C, F

C: E, G, H

D: F

E: B, F

F: A

G: E, H

H: A

Step 1 - First, push H onto the stack.

STACK: H

Step 2 - POP the top element from the stack, i.e., H, and print it. Now, PUSH all the neighbors of H onto the stack that are in ready state.

Print: H]STACK: A

Step 3 - POP the top element from the stack, i.e., A, and print it. Now, PUSH all the neighbors of A onto the stack that are in ready state.

Print: A  
STACK: B, D

Step 4 - POP the top element from the stack, i.e., D, and print it. Now, PUSH all the neighbors of D onto the stack that are in ready state.

Print: D  
STACK: B, F

Step 5 - POP the top element from the stack, i.e., F, and print it. Now, PUSH all the neighbors of F onto the stack that are in ready state.

Print: F  
STACK: B

Step 6 - POP the top element from the stack, i.e., B, and print it. Now, PUSH all the neighbors of B onto the stack that are in ready state.

Print: B  
STACK: C

Step 7 - POP the top element from the stack, i.e., C, and print it. Now, PUSH all the neighbors of C onto the stack that are in ready state.

Print: C  
STACK: E, G

Step 8 - POP the top element from the stack, i.e., G and PUSH all the neighbors of G onto the stack that are in ready state.

Print: G  
STACK: E

Step 9 - POP the top element from the stack, i.e., E and PUSH all the neighbors of E onto the stack that are in ready state.

Print: E  
STACK:

Now, all the graph nodes have been traversed, and the stack is empty.

The time complexity of the DFS algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the graph.

The space complexity of the DFS algorithm is O(V).

The Difference:

Breadth First Search	Depth First Search
BFS is a traversal approach in which we first walk through all nodes on the same level before moving on to the next level.	DFS is also a traversal approach in which the traverse begins at the root node and proceeds through the nodes as far as possible until we reach the node with no unvisited nearby nodes.
It uses Queues data structure to the shortest path	It uses stack data structure
It works with the concept of FIFO (First In First Out)	It works with the concept of LIFO (Last In First Out)
The Time complexity of BFS is O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used, where V stands for vertices and E stands for edges.	The Time complexity of DFS is also O(V + E) when Adjacency List is used and O(V^2) when Adjacency Matrix is used, where V stands for vertices and E stands for edges.
It is uses in bipartite graphs, shortest path etc.	It is used in acyclic graphs and topological order etc.
It uses more memory	It uses less memory