Depth First Search (DFS) Explained: Algorithm, Examples, and Code

Main ideas / lessons

• Graph traversal: Starting from a chosen vertex in a graph, a traversal is an algorithm that visits every vertex. Different traversals differ by the order in which vertices are visited.
• DFS (Depth-First Search) concept:
  • Explore “deeply” by continuing to visit newly discovered vertices.
  • When you can’t go further (a dead end), you backtrack (retrace steps) to find other unexplored options.
  • This “go until you hit a dead end, then backtrack” philosophy is the core intuition behind DFS.
• Multiple valid DFS orderings:
  • The exact order can vary depending on which neighbor you choose to explore next.
  • If a test asks for a specific DFS order, the choice rule must be defined (e.g., “choose the smallest-numbered neighbor first”).
• Preorder vs postorder:
  • Preorder DFS: output a vertex when it is first encountered.
  • Postorder DFS: output a vertex only after all of its neighbors have been fully explored (i.e., after backtracking from it).
• Implementation details:
  • DFS is naturally recursive at first, but it can also be implemented iteratively using a stack.
  • Both approaches require tracking visited/marked vertices to avoid infinite recursion or repeated work.
  • DFS runs in O(V + E) time (where V = vertices, E = edges) in both recursive and iterative forms.
• Applications of DFS (with modifications):
  • Cycle detection: detect a cycle by checking edges that point to already visited vertices (with the right criteria).
  • Connected components: run DFS from an unvisited vertex; repeat until all vertices are visited.
  • Topological sort (DAGs):
    • Use DFS post-order (with modifications/interpretation).
    • Key trick: reverse the post-order result to obtain a valid topological order.
  • Maze generation:
    • Model the maze as a graph (grid nodes).
    • Run a modified DFS from a start cell; randomly push neighbors onto the stack to carve out a maze.

Methodologies / instructions (detailed)

A) Building intuition for DFS traversal (walkthrough methodology)

• Start at a given start vertex.
• While there exists an unvisited neighbor from the current vertex:
  • Move to an unvisited neighbor (the “choice” can be arbitrary unless constrained).
• If you reach a dead end (no unvisited neighbors):
  • Backtrack to the previous vertex.
• Continue exploring until all vertices in the connected portion are visited.
• Repeat/backtrack until the traversal is confirmed to have visited every vertex.

B) Recursive DFS implementation (instruction steps)

• Inputs: graph G and starting vertex V
• Maintain a boolean array (or similar structure):
  • visited[u] = false initially for all vertices
  • set visited[u] = true once the vertex is visited

Algorithm structure:

• DFS(V):
  • mark visited[V] = true
  • for each neighbor u of V:
    • if visited[u] is false:
      • recursively call DFS(u)

Important fix vs naive recursion:

• Without visited, DFS may revisit the parent and cause infinite recursion.

C) Iterative DFS implementation using a stack (instruction steps)

• Maintain:
  • visited[] array (same as recursive)
  • a stack

Initialization:

• push the starting vertex onto the stack

Loop:

• while the stack is not empty:
  • pop a vertex x
  • if visited[x] is false:
    • mark visited[x] = true
    • iterate over neighbors of x
    • for each neighbor y:
      • if visited[y] is false, push y onto the stack

Note on duplicates:

• The same vertex may appear multiple times in the stack due to neighbor insertion, but the visited check prevents re-processing.

D) Converting preorder DFS to postorder DFS

• Start from the recursive preorder structure:
  • preorder: “visit/output” happens immediately on entering the DFS call.
• Modify for postorder:
  • delay the visit/output until after all recursive calls to neighbors finish.
• Equivalent implementation idea:
  • move the “record vertex” action to the end of the DFS function.

E) Applications: what modifications to use

1) Cycle detection using DFS

• Run DFS while tracking visited states.
• When DFS encounters an edge to a vertex that has already been visited (per the stated rule):
  • conclude that a cycle exists (with appropriate checking logic).

2) Connected components

• Keep all vertices initially unvisited.
• For each vertex not yet listed/visited:
  • start DFS from that vertex
  • the DFS will visit exactly one connected component
  • repeat until all vertices belong to some component.

3) Topological sort for DAGs

• Perform DFS post-order traversal.
• Collect the post-order list.
• Output the topological ordering as:
  • reverse(post-order)
• Rationale given:
  • The reversed post-order always yields a valid ordering for directed acyclic graphs (DAGs).

4) Maze generation using DFS

• Represent the maze grid as a graph.
• Start from a chosen cell (e.g., top-left).
• Use a modified DFS where neighbor selection is:
  • not deterministic one-by-one in a fixed order
  • instead, take the neighbor set and randomly insert neighbors into the stack
• The random neighbor pushing leads to a generated maze; difficulty depends on the randomization.

Sources / speakers featured

• No named speakers or external sources are identified in the subtitles. The content appears to be delivered by the video creator/instructor (unnamed).