GRAPH TRAVERSAL ALGORITHM

Mayank Aggarwal
7 min readMar 24, 2021

--

traversal means visiting every node of a graph only since and also in a defined manner

There are 2 algorithms for traversal that are

1 BFS which stands for breadth-first search traversal

2 DFS which stands for depth-first search traversal

BFS TRAVERSAL

BFS stands for breadth-first search traversal which is used to traverse the graph level wise it is also similar to level order traversal in the graph

HOW BFS WORKS

It begins the traversal with a given vertex, visits the entirety of the vertices near the first given vertex, and pushes them to a line arranged by visiting. At that point, it pops a component from the front of the line, visits the entirety of its neighbors and pushes the neighbors which are not previously visited into the line, and repeats the process until the line is unfilled or the entirety of the vertices are visited.

NEED OF BFS ALGORITHM

There are a lot of reasons to use the BFS algorithm some of the important reasons are as follows

1. BFS is valuable for examining the nodes in a graph and building the most limited way of traversing through these.

2. BFS can traverse through a graph in the most modest number of iterations.

3. The architecture of the BFS algorithm is basic and powerful.

4. The BFS algorithm's consequence holds an undeniable degree of exactness in contrast with different algorithms.

5. BFS iterations are consistent, and there is no chance of this algorithm becoming involved with a boundless circle issue.

6. it is also used in the pathfinding algorithm, for GPS navigation, in the minimum spanning tree.

ARCHITECTURE OF BFS ALGORITHM

LET'S UNDERSTAND THE WORKING OF BFS ALGORITHM WITH EXAMPLE

vertices in blue are unvisited and vertices in yellow are visited

step 1 we have take queue which is based on the FIFO principle and also we have taken visited array when we a particular index then we will change the adjacent value in the array from 0 to 1

step 2 we will mark 1 as visited and the value in the array will change from 0 to 1 and we have popped the element in the queue

step 3 we will pop the vertex 1 from the queue and print it

Step 4 we have seen that the vertices adjacent to 1 are not already visited so we visit them and push them into the queue and marks the visited in the visited array means we change the value corresponding to it from 0 to 1

Step 5 we will pop the vertex 2 from the queue and print it and then we will see that it has unvisited adjacent vertices so push 4 and 5 into the queue and marks them visited and also will change corresponding to it from 0 to 1

Step 6 we will pop vertex 3 from the queue and print it and check if there is any unvisited vertex is there or not as there is no unvisited adjacent vertex to 3 so we do not push anything to the queue

Step 7 we will pop the vertex 4 from the queue and will print it

Step 8 we will check that does vertex 4 has any unvisited vertex so we find that element 6 is adjacent unvisited vertex then will mark it as visited and the value in the array corresponding to 6 will become 1 from 0 and we element 6 will push in the queue

Step 9 we will POP the vertex 5 from the queue and will print it and as not vertex adjacent to vertex 5 left unvisited so we do not push any vertex to queue.

Step 10 we will POP vertex 6 and will print it from the queue and will check if it has any invited adjacent vertex so we will not push anything and the queue becomes empty

BFS PSEUDOCODE

BFS CODE IN PYTHON

TIME COMPLEXITY AND SPACE COMPLEXITY OF BFS ALGORITHM

TIME COMPLEXITY: O(V+E) where V indicates the no. of vertices and E indicates no of edges

SPACE COMPLEXITY: O(V)

REAL-LIFE APPLICATIONS OF BFS ALGORITHM

1 BFS algorithm can without much of a stretch make the briefest way and a minimum spanning tree to visit all the vertices of the graph in the most limited time conceivable with high exactness.

2 BFS can be executed to find all the closest or adjoining nodes in the P to P network This will track down the necessary information quicker.

3 BFS can help track down every adjoining area from the main or source area.

4 it is also used in web crawlers and network broadcasting.

DFS TRAVERSAL

DFS stands for depth-first search DFS traversal of a graph is used to traverse the graph depth wise it is a recursive algorithm used to search all vertices of a tree or graph.

Let's UNDERSTAND DFS WITH HELP of example

we have taken an undirected graph of 5 vertices

Step 1 we have visited vertex 0 and added it into the visited array and the adjacent unvisited vertex corresponding to 0 are put into the stack

Step 2 we have visited the element at the top of the stack which is 1 and will see if there is any unvisited vertex adjacent to 1 so vertex 2 is the unvisited adjacent vertex

Step 3 we will mark vertex 2 and visited and will see about the adjacent unvisited vertex to 2 so we got vertex 4 is unvisited adjacent vertex to the vertex 2 so we add vertex 4 into the top of the stack

Step 4 we will visit vertex 4 and mark it as visited

Step 5, at last, we will visit element 3 and we have seen that it does not contain any unvisited adjacent nodes and all the nodes are visited so DFS traversal is completed

DFS PSEUDOCODE

DFS CODE IN PYTHON

TIME AND SPACE COMPLEXITY OF DFS ALGORITHM

TIME COMPLEXITY of DFS algorithm is same as that of BFS algorithm which is O(V+E) where V indicates the no. of vertices and E indicates no of edges

SPACE COMPLEXITY of DFS algorithm is also same as of DFS algorithm that is O(V) where V indicated no. of vertices

REAL-LIFE APPLICATIONS OF DFS ALGORITHM

1 it is used to search the path between the 2 vertices.

2 it generates the shortest path tree and minimum spanning tree in a weighted graph

3 it is used to check that the graph is bipartite and also used for finding the path also used to find the strongly connected components in the graph

DIFFERENCE BETWEEN DFS AND BFS ALGORITHM

1 BFS uses queue data structure so it is implemented using FIFO list while DFS uses stack data structure so it implements using the LIFO list

2 BFS tracks down the shortest way to the destination through DFS goes to the lower part of a subtree, at that point backtracks.

3 DFS traverse according to tree depth while BFS acc to tree level

4 There is no need for backtracking in BFS while in DFS backtracking is needed.

THANKS FOR READING

--

--