The Tech Platform
Nov 29, 20224 min
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.
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
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}
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.
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
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 Tech Platform