Depth-first traversal is a method of traversing graphs which explores a path as far as possible before backtracking to explore alternative paths. Depth-first traversal is a generalization of depth-first tree traversal to graphs.

Depth-first traversal is typically implemented using recurssion or an explicit stack.

Implementation

Assume the graph is represented using an adjacency list.

def depth_first_traversal(graph, start, visit):
    visited = set()

    def dfs(v):
        visited.add(v)
        visit(v)

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

    dfs(start)

• Vertices are visited when first discovered
• Traversal follows one path until no unvisited neighbours remain
• Backtracking occurs via the call stack

This visits exactly the vertices in the connected component containing start.

Traversing an Entire Graph

def depth_first_traversal_all(graph, visit):
    visited = set()

    def dfs(v):
        visited.add(v)
        visit(v)

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

    for v in graph:
        if v not in visited:
            dfs(v)

• Ensures all vertices are visited
• Each connected component produces a DFS tree