Depth-First Search (DFS) is a fundamental graph traversal technique used in computer science. It explores as far as possible along each branch before backtracking. This tutorial will guide you through the basics of DFS, its implementation, and its applications.

Basic Concepts

  • Graph: A collection of nodes (vertices) and edges connecting these nodes.
  • Node: A point of interest in the graph.
  • Edge: A connection between two nodes.
  • Traversal: Visiting all nodes in the graph.

How DFS Works

DFS uses a stack to keep track of nodes to visit. It starts at a given node and explores as far as possible along each branch before backtracking.

Steps of DFS

  1. Start at a given node.
  2. Mark the node as visited.
  3. Explore all unvisited neighbors of the current node.
  4. For each unvisited neighbor, repeat steps 2-4.
  5. If no unvisited neighbors, backtrack to the previous node.

Implementation

Here's a basic implementation of DFS in Python:

def dfs(graph, start):
    visited = set()
    stack = [start]

    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            # Process the node
            print(node)
            # Add unvisited neighbors to the stack
            stack.extend(graph[node] - visited)

Applications

DFS has various applications, such as:

  • Finding connected components: Identifying groups of nodes that are connected.
  • Cycle detection: Detecting cycles in a graph.
  • Pathfinding: Finding the shortest path between two nodes.

Additional Resources

For more information on DFS and graph traversal techniques, check out our Graph Traversal Techniques tutorial.

Image:

Algorithm_Graph