Depth-first search

Depth-first search goes as far as it can along one path, then backs up and tries the next way. It does not find shortest routes. What it gives instead is structure: the order in which vertices finish, and a label for every edge. Cycles (lesson 4), task orders (lesson 5) and the connectivity station (CONN) all read that structure.

Going deep first

TREE-2 walked a tree in pre-order and post-order with recursion. Depth-first search (DFS) is the same walk on a graph, plus a mark on every vertex already reached, so it never goes round a cycle again and again:

def dfs_all(adj):
    n = len(adj)
    d = [0] * n                 # discovery time; 0 means not reached
    f = [0] * n                 # finish time
    time = 0

    def visit(u):
        nonlocal time
        time += 1
        d[u] = time             # u is discovered
        for v in adj[u]:
            if d[v] == 0:
                visit(v)        # go deeper first
        time += 1
        f[u] = time             # every neighbour tried: u finishes

    for s in range(n):          # every vertex, even ones s cannot reach
        if d[s] == 0:
            visit(s)
    return d, f

A vertex is discovered when the search first reaches it, and finishes when all its neighbours have been tried. In between, it sits on the current path: the chain of calls that are waiting. Each vertex is visited once and each list is read once, so DFS costs O(V + E), like BFS. The figure keeps one clock for both events and shows each vertex’s times as a tag, discovery/finish.

Discovery and finish times

Think of each vertex as holding the time span from its discovery to its finish. Two facts about these spans are the base of every proof in this station.

Take two vertices u and v, with u discovered first. If v is discovered while u is still on the path, v is below u in the search, and calls end in the reverse order they began (STAQ-1), so v finishes before u: v’s span is inside u’s. Otherwise u had already finished when v was discovered, and the spans are apart. So v is below u in the search (a descendant) exactly when v’s span is inside u’s.

If v ends up below u, the path of calls from u down to v was made of vertices discovered after u, so they were not reached at that moment. For the other direction, suppose such a free path exists but some vertex on it does not end up below u; take the first one, w. The vertex just before w on the path is below u (or is u), so the search tries the edge to w before that vertex finishes, and therefore before u finishes. w was not reached when u began, so it is discovered inside u’s span, which puts it below u, a contradiction.

Four kinds of edges

When the search looks along an edge u → v, the state of v sorts the edge into one of four kinds:

• Tree edge: v is not reached yet, and the search goes to v. The tree edges form the DFS forest: one tree per fresh start.
• Back edge: v is still on the path, so v is above u. The edge leads back up.
• Forward edge: v is finished and was discovered after u, so v is already below u, reached by another way.
• Cross edge: v is finished and was discovered before u. Neither is above the other.

In an undirected graph only tree edges and back edges occur. An edge u–v is looked at from both ends, and whichever end is discovered first still has the edge to try while the other end is being searched, so the later one is always below the earlier one.

Without recursion

Each recursive call uses room on Python’s call stack, and Python stops at 1,000 nested calls by default (sys.getrecursionlimit()). A path of 100,000 vertices is common in real input. sys.setrecursionlimit lets Python go deeper, but the call stack underneath is fixed in size, and when it runs out the program crashes without a Python error. In the browser the limit is lower still. So a DFS that must handle any input keeps its own stack in a list.

The short version pushes all neighbours and pops one at a time:

def dfs_visit_order(adj, s):
    seen = [False] * len(adj)
    order = []
    stack = [s]
    while stack:
        u = stack.pop()
        if seen[u]:
            continue            # pushed twice, by two neighbours
        seen[u] = True
        order.append(u)
        for v in reversed(adj[u]):   # so adj[u][0] is popped first
            if not seen[v]:
                stack.append(v)
    return order

This visits vertices in the same order as the recursion, but it has no moment when a vertex finishes, and a vertex can sit on the stack several times (the stack can hold E entries). To copy the recursion exactly, keep on the stack what a paused call keeps: the vertex, and how far through its list it has got. A Python iterator remembers exactly that: push (u, iter(adj[u])), take the next neighbour from the iterator on top, and when the iterator is empty, u finishes. The figure’s second variant shows this stack, with each vertex’s next neighbour; it holds the same vertices as the call stack. P3 asks you to write it.

Connected parts

In an undirected graph, each fresh start of the search reaches exactly one connected component: a largest group of vertices that are joined by paths. Counting fresh starts counts components, in O(V + E). DSUF-5 counts them with union-find, which is better when edges arrive one at a time and the count is wanted after each one. A search is better when you also need the paths, the order, or the times.

Now try GRPH-P3, Finish order.