Applications of Depth-First Search (DFS)

Depth-First Search (DFS) is used as a fundamental building block for solving several complex graph problems. Below are the primary applications of DFS.

1. Cycle Detection in Graphs

• Undirected Graph: A cycle exists if we encounter an already-visited vertex that is not the direct parent of the current vertex during our traversal.
• Directed Graph: We use a recursion stack tracker to detect back-edges. If we find a neighbor that is already present in the active recursion stack, a cycle is present.

2. Path Finding (Source to Destination)

We can easily adapt DFS to find a path between a source vertex u and a destination vertex z:

1. Start DFS at u.
2. Push nodes onto a path stack as we visit them.
3. If we reach z, the path stack contains the complete path from u to z.
4. If a branch fails to reach z, pop the vertex from the stack during backtracking.

3. Topological Sorting

Used for scheduling tasks with dependencies (e.g. build systems, job scheduling, or spreadsheets recalculation). In a Directed Acyclic Graph (DAG), topological sorting orders vertices such that for every directed edge u -> v, vertex u comes before v.

• How DFS is used: Run DFS on the graph. Once a vertex has no unvisited neighbors (all its outgoing paths are explored), push it onto a stack. The final stack popped from top-to-bottom gives the topological order.

4. Testing if a Graph is Bipartite

A bipartite graph can be colored using only 2 colors such that no two adjacent vertices share the same color. During DFS traversal:

• Color the start node with Color 1.
• For every unvisited neighbor, color it with the opposite color (Color 2).
• If we encounter an already-colored neighbor with the same color as the current vertex, the graph is not bipartite.

5. Finding Strongly Connected Components (SCC)

A directed graph is strongly connected if there is a path from any vertex to every other vertex.

• DFS is used in Kosaraju's Algorithm and Tarjan's Algorithm to group vertices into SCCs.
• Kosaraju's Algorithm uses a initial DFS to order vertices, transposes/reverses the graph, and runs a second DFS in the sorted order to isolate components in $O(V + E)$ time.

6. Solving Mazes and Puzzles

For puzzles with a single exit (like mazes):

• Nodes represent intersections, and edges represent paths.
• DFS automatically searches deep into paths.
• By keeping track of only the current path in the recursion visited stack, we can backtrack immediately if we hit a wall and find the correct solution.