DFS

Depth-First Search (DFS) is another fundamental graph traversal algorithm, which explores as far as possible along each branch before backtracking. It uses a stack data structure, either explicitly or implicitly with recursion. DFS is useful for many applications, including pathfinding, cycle detection, and topological sorting.

DFS Algorithm

1. Initialization:
   • Choose a starting node (source node).
   • Create a stack and push the source node onto it.
   • Mark the source node as visited.
2. Traversal:
   • While the stack is not empty:
     • Pop a node from the stack (let’s call it current_node).
     • For each unvisited neighbor of current_node:
       • Mark the neighbor as visited.
       • Push the neighbor onto the stack.

Pseudocode

Here is a simple pseudocode for DFS:

Iterative Approach:

DFS(Graph, start_node):
    create a stack S
    mark start_node as visited
    push start_node onto S

    while S is not empty:
        current_node = S.pop()
        for each neighbor of current_node:
            if neighbor is not visited:
                mark neighbor as visited
                push neighbor onto S

Recursive Approach:

DFS(Graph, current_node, visited):
    mark current_node as visited
    for each neighbor of current_node:
        if neighbor is not visited:
            DFS(Graph, neighbor, visited)

Example

Consider the following graph:

   A
  / \
 B   C
 |   |
 D   E
  \ /
   F

If we start DFS from node A, the steps would be:

1. Push A onto the stack and mark it as visited.
2. Pop A, push its neighbors B and C onto the stack, and mark them as visited.
3. Pop C, push its neighbor E onto the stack, and mark it as visited.
4. Pop E, push its neighbor F onto the stack, and mark it as visited.
5. Pop F.
6. Pop B, push its neighbor D onto the stack, and mark it as visited.
7. Pop D.

The order of visited nodes could be: A -> C -> E -> F -> B -> D.

Applications

• Pathfinding: DFS can be used to find a path from the source to the destination in a graph.
• Cycle Detection: DFS can detect cycles in both directed and undirected graphs.
• Topological Sorting: In a directed acyclic graph (DAG), DFS can be used to perform a topological sort.
• Connected Components: DFS can identify connected components in a graph.
• Solving Puzzles: DFS can solve puzzles like mazes, where you need to explore all possibilities to find a solution.