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