GRAPH TRAVERSAL ALGORITHM
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
