Python programs / Graphs / Depth-first search

Python Program for Depth-First Search (DFS)

Intermediate Graphs Time O(V + E) Space O(V)

Visits the nodes of a graph from a start node, following each path as deep as it goes before backing up to try the next.

Depth-first search (DFS) explores a graph the way you might explore a maze: follow one path as far as it goes, and only at a dead end go back to the last junction and try the next way. The program's graph has six nodes and six edges (A–B, A–C, B–D, B–E, C–F and E–F). From A, DFS goes to B and then D, where it hits a dead end, backs up to B and goes on through E and F to C: A, B, D, E, F, C. Breadth-first search on the same graph goes ring by ring instead: A, B, C, D, E, F. DFS is the starting point for many graph programs: checking whether two nodes are connected, finding cycles, ordering tasks and solving puzzles.

Program

def dfs(graph, start):
    """Every node reachable from start, in depth-first order."""
    order = []
    seen = set()

    def visit(node):
        seen.add(node)
        order.append(node)
        for neighbour in graph[node]:
            if neighbour not in seen:
                visit(neighbour)  # go deeper before the next one

    visit(start)
    return order


# Each node, and the nodes it's joined to by an edge
graph = {
    "A": ["B", "C"],
    "B": ["A", "D", "E"],
    "C": ["A", "F"],
    "D": ["B"],
    "E": ["B", "F"],
    "F": ["C", "E"],
}
print("DFS from A:", dfs(graph, "A"))

Open in the editor Download depth_first_search.py

Output

DFS from A: ['A', 'B', 'D', 'E', 'F', 'C']

How it works

  1. order collects the nodes in the order they are visited, and seen is a set of the nodes visited so far, which answers "is it in here?" at once.
  2. visit() is a function inside dfs(), so it can use order and seen without being passed them (scope). Visiting a node marks it as seen and adds it to the order.
  3. Then visit() calls itself for each neighbour not seen yet (recursion). That call doesn't return until it has explored everything it can reach, so the search goes as deep as it can before it moves on to the next neighbour.
  4. dfs() starts the search at start, and once every call has finished, returns the order.
  5. The graph is a dictionary: each node is a key, and its value is the list of nodes it's joined to. An edge goes both ways, so it's listed twice: B is in A's list and A is in B's.
  6. The program prints the order DFS visits the nodes in, starting from A.

Each visit, with the calls still running when it happens:

Step Visits Calls still running Then
1 A A B is the first neighbour not seen
2 B A → B A is seen, so on to D
3 D A → B → D Its only neighbour, B, is seen: back to B
4 E A → B → E B is seen, so on to F
5 F A → B → E → F On to C
6 C A → B → E → F → C A and F are seen: the calls return one by one

When the calls get back to A, its second neighbour, C, has been visited already, so the search is over.

Time and space complexity

TimeO(V + E)
Extra spaceO(V)

visit() runs once for each node the start can reach, as a node is marked seen before anything else and never visited again: at most V calls for a graph of V nodes. Each call reads its node's neighbour list once, and the lists together hold every edge twice (once from each end), so the loops run about 2E times in all for E edges. Together that's O(V + E). seen and order hold up to V nodes, and on a graph shaped like a long chain the calls still running can reach V too, so the extra space is O(V).

Other ways to write it

With a stack instead of recursion

A list used as a stack does the calls' job: pop() takes the node added last, so the newest path is followed first. A node can go on the stack more than once before it's visited, so it's checked when it comes off. Pushing the neighbours in reverse gives the same order as the recursive version. This version also avoids Python's limit of about 1,000 calls running at once, which a graph with a long chain of nodes could reach.

def dfs(graph, start):
    order = []
    seen = set()
    stack = [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for neighbour in reversed(graph[node]):
            if neighbour not in seen:
                stack.append(neighbour)
    return order

graph = {"A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "F"],
         "D": ["B"], "E": ["B", "F"], "F": ["C", "E"]}
print(dfs(graph, "A"))

Try it yourself

  • Start from F instead of A. The order is F, C, A, B, D, E.
  • Swap the neighbours in A's list, "A": ["C", "B"], and run it again: the order becomes A, C, F, E, B, D. A graph can have more than one depth-first order, depending on which neighbour is tried first.
  • Give visit() a second argument, depth, starting at 0 and one more for each neighbour, and print each node indented by two spaces per level. The indents show the tree the search draws: D and E both under B, then F under E and C under F.
  • Add two nodes joined only to each other, "G": ["H"] and "H": ["G"]. DFS from A never reaches them. Change the function so that it starts a new search from every node not seen yet, and count how many searches it takes: that's the number of separate groups, 2.

More graphs programs

Share this program