This algorithm selects a single node (initial or source point) in a graph and then visits all the nodes adjacent to the selected node. Once the algorithm visits and marks the starting node, then it moves towards the nearest unvisited nodes and analyses them. Once visited, all nodes are marked. These iterations continue until all the nodes of the graph have been successfully visited and marked. The full form of BFS is the Breadth-first search.
What is DFS?
DFS is an algorithm for finding or traversing graphs or trees in depth-ward direction. The execution of the algorithm begins at the root node and explores each branch before backtracking. It uses a stack data structure to remember, to get the subsequent vertex, and to start a search, whenever a dead-end appears in any iteration. The full form of DFS is Depth-first search.
Difference between BFS and DFS Binary Tree
Here are the important differences between BFS and DFS.
Example of BFS
In the following example of BFS, we have used graph having 6 vertices. Example of BFS Step 1)
You have a graph of seven numbers ranging from 0 – 6. Step 2)
0 or zero has been marked as a root node. Step 3)
0 is visited, marked, and inserted into the queue data structure. Step 4)
Remaining 0 adjacent and unvisited nodes are visited, marked, and inserted into the queue. Step 5)
Traversing iterations are repeated until all nodes are visited.
Example of DFS
In the following example of DFS, we have used an undirected graph having 5 vertices.
Step 1)
We have started from vertex 0. The algorithm begins by putting it in the visited list and simultaneously putting all its adjacent vertices in the data structure called stack. Step 2)
You will visit the element, which is at the top of the stack, for example, 1 and go to its adjacent nodes. It is because 0 has already been visited. Therefore, we visit vertex 2. Step 3)
Vertex 2 has an unvisited nearby vertex in 4. Therefore, we add that in the stack and visit it. Step 4)
Finally, we will visit the last vertex 3, it doesn’t have any unvisited adjoining nodes. We have completed the traversal of the graph using DFS algorithm.
Applications of BFS
Here, are Applications of BFS:
Un-weighted Graphs:
BFS algorithm can easily create the shortest path and a minimum spanning tree to visit all the vertices of the graph in the shortest time possible with high accuracy.
P2P Networks:
BFS can be implemented to locate all the nearest or neighboring nodes in a peer to peer network. This will find the required data faster.
Web Crawlers:
Search engines or web crawlers can easily build multiple levels of indexes by employing BFS. BFS implementation starts from the source, which is the web page, and then it visits all the links from that source.
Network Broadcasting:
A broadcasted packet is guided by the BFS algorithm to find and reach all the nodes it has the address for.
Applications of DFS
Here are Important applications of DFS:
Weighted Graph:
In a weighted graph, DFS graph traversal generates the shortest path tree and minimum spanning tree.
Detecting a Cycle in a Graph:
A graph has a cycle if we found a back edge during DFS. Therefore, we should run DFS for the graph and verify for back edges.
Path Finding:
We can specialize in the DFS algorithm to search a path between two vertices.
Topological Sorting:
It is primarily used for scheduling jobs from the given dependencies among the group of jobs. In computer science, it is used in instruction scheduling, data serialization, logic synthesis, determining the order of compilation tasks.
Searching Strongly Connected Components of a Graph:
It used in DFS graph when there is a path from each and every vertex in the graph to other remaining vertexes.
Solving Puzzles with Only One Solution:
DFS algorithm can be easily adapted to search all solutions to a maze by including nodes on the existing path in the visited set.
