Exploring Variants of DFS Algorithms: A Comprehensive Guide
Depth-First Search (DFS) is a fundamental algorithm used in graph theory, which is a method for traversing or searching tree or graph data structures. The algorithm starts at the root and explores as far as possible along each branch before backtracking.
There are several variants of the DFS algorithm, which include:
Recursive DFS
This is the most straightforward version of DFS. It uses the system stack during the recursion process. It starts from the root node, explores the adjacent nodes at first, and if the adjacent node has any unvisited node, it continues the same process.
Iterative DFS (Using stack)
This variant uses a user-defined stack to avoid system stack overflow. It is particularly useful for large graphs. It uses a LIFO queue (stack) to select the next vertex to start a search when a dead end is reached.
Bipartite Checking DFS
This variant is used to check whether a given graph is bipartite or not. A bipartite graph is a graph whose vertices can be divided into two disjoint and independent sets such that every edge connects a vertex in the first set to one in the second set.
A bipartite graph, also known as a bigraph, is a type of graph where the vertex set can be split into two disjoint sets such that every edge in the graph connects a vertex from the first set to a vertex in the second set. In other words, there are no edges that connect vertices within the same set.
The two disjoint sets are often referred to as the left and right, or top and bottom, of the graph.
An important characteristic of bipartite graphs is that they do not contain any odd-length cycles. This property can be used to determine whether a graph is bipartite or not.
Bipartite graphs are used in many real-world applications, including matching problems, scheduling problems, and in the construction of network models. For example, in a job scheduling problem, one set of vertices could represent jobs and the other set could represent workers. An edge between a job and a worker could represent that the worker is qualified to perform the job.
Topological Sorting DFS
Topological sorting for a directed acyclic graph (DAG) is a linear ordering of vertices such that for every directed edge u -> v, vertex u comes before v in the ordering. Topological Sorting for a graph is not possible if the graph is not a Directed Acyclic Graph (DAG).
Here’s a simple example: if you’re doing a task-based project, some tasks may depend on other tasks being completed first. Topological sorting would provide an order of tasks so that all tasks are completed in a valid sequence.
The topological sort algorithm takes a directed graph as input and returns an array of the nodes as the output, representing the topological order.
This variant is used for topological sorting in a directed graph. Topological Sorting for a graph is not possible if the graph is not a Directed Acyclic Graph (DAG).
Strongly Connected Components DFS (Kosaraju’s Algorithm)
This variant is used to find all strongly connected components in a graph. A directed graph is strongly connected if there is a path between all pairs of vertices.
DFS for a Tree (Edge Classification)
This variant is used in a tree instead of a graph to classify the edges into a tree edge, forward edge, cross edge, and back edge.
- Validate Binary Search Tree (LeetCode 98)
- Construct Binary Tree from Preorder and Inorder Traversal (LeetCode 105)
DFS for a n-ary Tree (Print all paths)
This variant is used in an n-ary tree (a tree where each node can have no more than n children) to print all the paths from the root node to the leaf nodes.
DFS for Water Jug problem
This variant is used to solve the water jug problem where you have to measure a specific amount of water using two jugs of different capacities.
DFS for Disconnected Graph
This variant is used when the graph is disconnected. It explores the disconnected components of the graph.
