Depth‑First Search (DFS)　Classic AI Algorithms

By |
0 Comment
  1. DFS explores a graph by going as deep as possible before back‑tracking.
  2. It can be written recursively (uses the call stack) or iteratively (uses an explicit stack).
  3. The Python snippet above demonstrates a clean recursive DFS on an adjacency‑list representation, plus an iterative alternative.
  4. Because we keep a visited set, the algorithm safely handles graphs that contain cycles.

Simple Python Example

The code below shows a recursive DFS on an undirected graph represented as an adjacency list.
Vertices are numbered starting from 0.

# -------------------------------------------------
# 1. Define the graph as an adjacency list
# -------------------------------------------------
graph = {
    0: [1, 2],          # 0 is connected to 1 and 2
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1],
    5: [2],
    6: []               # an isolated node (optional)
}

# -------------------------------------------------
# 2. Recursive DFS implementation
# -------------------------------------------------
def dfs_recursive(v, visited, graph, order):
    """
    v        : current vertex
    visited  : set of already‑visited vertices
    graph    : adjacency list dictionary
    order    : list that records the visitation order
    """
    visited.add(v)
    order.append(v)               # record the visit
    for nxt in graph[v]:          # explore neighbours
        if nxt not in visited:    # only recurse on unvisited nodes
            dfs_recursive(nxt, visited, graph, order)

# -------------------------------------------------
# 3. Run DFS on every connected component
# -------------------------------------------------
def dfs_all(graph):
    visited = set()
    order   = []                    # overall visitation order
    for v in graph:                 # start from each vertex
        if v not in visited:
            dfs_recursive(v, visited, graph, order)
    return order

# -------------------------------------------------
# 4. Execute and print the result
# -------------------------------------------------
if __name__ == "__main__":
    result = dfs_all(graph)
    print("DFS visitation order :", result)

Expected output

DFS visitation order : [0, 1, 3, 4, 2, 5, 6]
  • Starting from vertex 0, the algorithm dives deep into 1 → 3 → 4, then backtracks to explore 2 → 5, and finally visits the isolated node 6.

Iterative (stack‑based) version

If you prefer an explicit stack (e.g., to avoid Python’s recursion limit), here’s a compact iterative version:

def dfs_iterative(start, graph):
    visited = set()
    stack   = [start]          # LIFO stack
    order   = []

    while stack:
        v = stack.pop()
        if v in visited:
            continue
        visited.add(v)
        order.append(v)

        # Adding neighbours in reverse order keeps the same visitation order
        # as the recursive version when we pop from the stack.
        for nxt in reversed(graph[v]):
            if nxt not in visited:
                stack.append(nxt)

    return order

# Example usage
print(dfs_iterative(0, graph))   # → [0, 1, 3, 4, 2, 5, 6]

Both implementations produce the same visitation order; choose the style that best fits your problem size and coding preferences.