Graph Traversal: Depth-First Search (DFS) Examples

Explore practical examples of Depth-First Search (DFS) in graph traversal, demonstrating its applications and variations.
By Jamie

Introduction to Depth-First Search (DFS)

Depth-First Search (DFS) is a fundamental algorithm used for traversing or searching through graph structures. It explores as far as possible along each branch before backtracking, making it particularly useful for scenarios where you want to explore all possibilities. DFS can be implemented using recursion or an explicit stack, and it finds applications in solving puzzles, analyzing networks, and exploring pathways in mazes.

Example 1: Maze Solving Using DFS

In this example, we’ll demonstrate how DFS can be employed to find a path through a maze. Imagine a simple maze represented as a grid, where walls are denoted by 1 and open paths by 0.

To solve the maze using DFS, we can treat the maze as a graph where each cell is a node connected to its adjacent cells (up, down, left, right). Starting from the entrance, we will explore each path until we either find the exit or exhaust all options.

Maze Grid Representation:

1 1 1 1 1 1 1
1 0 0 1 0 0 1
1 1 0 1 1 0 1
1 0 0 0 0 0 1
1 1 1 1 1 1 1

Procedure:

  1. Start from the entrance (1, 1).
  2. Mark the cell as visited.
  3. Recursively explore each unvisited neighboring cell.
  4. Backtrack if you reach a dead end or find the exit.
  5. Continue until the exit is found.

Notes:

  • DFS is particularly effective for this application because it allows for exploring deep into the maze before needing to backtrack.
  • A variation could involve implementing pathfinding heuristics to optimize the search further.

Example 2: Topological Sorting of a Directed Acyclic Graph (DAG)

Topological sorting is another important application of DFS, particularly in scenarios involving scheduling tasks or organizing processes. A directed acyclic graph (DAG) represents dependencies between tasks, where an edge from node A to node B indicates that task A must be completed before task B.

Task Dependency Graph:

A --> B
A --> C
B --> D
C --> D
C --> E
D --> F

Procedure:

  1. Perform DFS on the graph.
  2. Upon visiting a node, add it to the front of a list (or stack).
  3. Continue until all nodes are visited.
  4. The resulting list will represent a valid order of tasks.

Notes:

  • If the graph has cycles, topological sorting is not possible.
  • Variations can include Kahn’s algorithm, which uses indegrees and a queue instead of DFS.

Example 3: Finding Connected Components in an Undirected Graph

In many real-world applications, such as social networks or networks of computers, it’s essential to identify connected components, which are subsets of nodes that are all reachable from one another. DFS can effectively identify these components in an undirected graph.

Undirected Graph Representation:

A -- B
|    |
C -- D   E -- F

Procedure:

  1. Initialize a visited set to track visited nodes.
  2. Iterate through each node in the graph.
  3. If a node has not been visited, initiate a DFS from that node.
  4. Mark all reachable nodes during this DFS as belonging to the same connected component.
  5. Repeat until all nodes have been visited.

Notes:

  • The result will be a collection of connected components.
  • This method can also be used to analyze the structure of social networks or biological systems.
  • Variations may include counting the number of connected components or identifying articulation points.