Depth First Search Traversal Order in Python

Recursive depth-first search that returns the visit order of nodes in an adjacency list graph starting from a given node.

Easy Python 3.9+ Aug 9, 2026 Algorithms & data structures 15 views 0 copies

dfs graph traversal adjacency-list recursion

Python code

28 lines

Python 3.9+

def dfs_order(adj, start):
    visited = set()
    order = []

    def dfs(node):
        visited.add(node)
        order.append(node)
        for neighbor in adj.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)
    return order


if __name__ == "__main__":
    # Demo graph: adjacency list representation
    graph = {
        'A': ['B', 'C'],
        'B': ['A', 'D', 'E'],
        'C': ['A', 'F'],
        'D': ['B'],
        'E': ['B', 'F'],
        'F': ['C', 'E']
    }

    result = dfs_order(graph, 'A')
    print(result)

Output

stdout

['A', 'B', 'D', 'E', 'F', 'C']

How it works

This DFS implementation uses a nested dfs function that marks each node as visited when first encountered, then appends it to the order list. It recursively explores all unvisited neighbors from the adjacency list. The visited set prevents infinite loops in cyclic graphs by tracking nodes already processed. The function returns the complete traversal order, which depends on neighbor ordering in the adjacency dict.

Common mistakes

Forgetting to mark a node as visited before exploring its neighbors, causing infinite recursion in cycles
Using recursion without considering Python's recursion limit for very deep graphs
Assuming input graph is a list of tuples instead of using adjacency list format

Variations

Implement DFS iteratively using an explicit stack: `stack = [start]; while stack: node = stack.pop()`
Use a `collections.defaultdict(list)` to simplify handling missing keys in the adjacency list

Real-world use cases

Discovering all reachable nodes in a social network from a starting user to determine connection clusters.
Topological sorting of dependencies in a build system by processing nodes in reverse DFS order.
Finding connected components in an undirected graph by running DFS from unvisited nodes.

Depth First Search Traversal Order in Python

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Tutorials

Quizzes

Python code

Output

How it works

Common mistakes

Variations

Real-world use cases

More from Algorithms & data structures

Keep learning

Tutorials

Quizzes