Depth First Search Algorithm

Depth First Search (DFS) is a graph traversal algorithm that explores as far as possible along each branch before backtracking. It is used to traverse or search tree or graph data structures.

Algorithm

The DFS algorithm works by visiting a node and then recursively visiting each of its neighbors. It keeps track of visited nodes to avoid revisiting them and uses a stack to store the nodes to be visited.

The algorithm can be implemented using either a recursive or iterative approach. The recursive approach is simpler and more intuitive, while the iterative approach uses an explicit stack to simulate the function call stack.

Recursive Implementation

The recursive implementation of DFS is straightforward and easy to understand. It involves defining a recursive function that visits a node and recursively visits its neighbors.

from typing import List

def dfs(graph: List[List[int]], start: int, visited: List[bool]):
    visited[start] = True
    print(start, end=' ')

    for neighbor in graph[start]:
        if not visited[neighbor]:
            dfs(graph, neighbor, visited)

graph = [[1, 2], [0, 3, 4], [0, 5], [1], [1], [2]]
visited = [False] * len(graph)
dfs(graph, 0, visited) # 0 1 3 4 2 5