Graph Traversal

Depth-first search (DFS)

Depth-first search follows a route as far as possible. At a dead end it backtracks; if it encounters an unexplored branch while returning, it descends that branch.

Imagine a small town where each location holds a light orb that grants a wish. Starting at location 0, explore the town to collect all the orbs.

Binary-tree preorder is a form of depth-first traversal. Backtracking can use an explicit last-in-first-out stack or recursion, whose calls also use a stack.

Depth-first search

dfs(Vertex V)
    isVisited[V] = true
    for v in neighbors(V)
        if !isVisited[v]
            DFS(v)

Breadth-first search (BFS)

Instead of following one route to its end, breadth-first search visits neighbors of the source first, then slightly farther vertices, then more distant ones.

Binary-tree level order is a form of breadth-first traversal. A queue provides the needed order.

Breadth-first search

bfs(Vertex V)
    isVisited[V] = true
    enqueue(Q, V)
    while !isEmpty(Q)
        V = dequeue(Q)
        for v in neighbors(V)
            if !isVisited[v]
                isVisited[v] = true
                enqueue(Q, v)