DAA: Application of DFS and BFS

Application of DFS and BFS

Depth-first search and breadth-first searches are the most famous algorithms used in daily life and the programming world. Let us now explore each application in which these algorithms are used as a building block:

DFS Applications

1. DFS of a graph produces the minimum spanning tree and pair of all shortest-path trees.
2. Detects a cycle in a graph; A graph contains cycle if there exists a back edge for a node. This can be done with a depth-first search algorithm because we when we can maintain the backtrack in DFS, we can maintain the back edge.
3. To find the path between cities: The DFS algorithm finds the path between two vertices(u and v) by the following method:

• U is the initial vertex.
• Maintain a stack to count the current vertex from the start.
• When we reach v, pop the stack, which will be the path from u to z.

    4)  Topological sorting: In this sorting, we schedule jobs from the given dependencies among jobs. In computer science, applications of this type arise in instruction scheduling, ordering formula cell evaluation when recomputing formula values in spreadsheets, logic synthesis, determining the order of compilation tasks to perform in makefiles, data serialization, and resolving symbol dependencies in linkers.

5) DFS algorithm also checks if a graph is bipartite or not.

6)  Using DFS, we can find the strongly connected components in a graph. Strongly connected components are the ones that are connected to every node in the graph.

7) We can solve maze puzzles with the DFS algorithm’s help as it can be implemented to find all possible paths to a maze end by only including nodes on the visited set’s current path.

8) The bridges in a graph can be found using DFS.

9) It is also used in planarity testing and finding biconnectivity in graphs.

10) It is also used to generate words in order to plot the limit set of a group.

BFS Applications

1.  Shortest Path and MST for unweighted graph: The path with the least number of edges is the shortest path. With the help of BFS, we can reach a vertex from a given source using the minimum number of edges. We can also use DFS or BFS to find a spanning tree in the unweighted graph.
2. To find all neighbor nodes BFS can be a great help. It is useful in finding the peer to peer networks. Example - BitTorrent
3. The crawlers in the search engine use the BFS approach. The idea used behind it is to start from the source page and repeat it. DFS can also be used for crawlers, but it has some limits.
4. DFS is also used in social networking websites where we see a mutual friend in the friend list, and we can search anyone via mutual connections.
5. BFS is also helpful in navigation as it is easier to find the neighboring locations on maps.
6. In broadcasting, a packet uses the BFS algorithm to reach all the destinations.
7. It is also used in Chenney’s algorithm in garbage collection. Due to better locality of reference, we use BFS over DFS.
8. The cycle detection can be done using BFS or DFS. For weighted graphs, BFS helps in cycle detection.
9. The BFS algorithm is beneficial in the ford-Fulkerson algorithm to find the maximum flow because it reduces O’s time complexity(VE^2).
10. The BFS algorithm also checks the bipartiteness of a graph.
11. To find all the reachable nodes from a given node BFS is much beneficial.