Study guides · Introductory

Understand BFS and DFS through traversal order and shortest paths

Define vertices, edges, visited state, and edge weights before choosing a graph traversal for the question you need to answer.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Define the graph and the objective
  2. BFS expands distance layers
  3. DFS explores a branch and returns
  4. Weights and representations change the problem
  5. Ask Logeia about this articleCheck your understanding

Define the graph and the objective

Stations and routes, pages and links, or tasks and dependencies can become graphs. Direction and weight still require explicit meanings. A directed link does not necessarily permit movement in both directions. Decide what a vertex represents, which transitions exist, and what quantity a shortest path should minimize.

Reachability, fewest edges, and minimum total travel time are different objectives. Choose an algorithm only after stating the objective and input assumptions. Also decide how to handle isolated vertices, missing references, self-loops, and duplicate edges. These are part of the data model, not inconvenient details to ignore.

BFS expands distance layers

Breadth-first search normally uses a queue to process vertices in increasing layers from a start. When every edge has the same cost, it can find minimum edge counts. Marking a vertex discovered when enqueuing it prevents multiple predecessors from repeatedly adding the same vertex.

Suppose A has edges to B and C, and C also has an edge to B. B already has distance one when A discovers it. Finding B again from C does not require another insertion. Recording predecessors as well as distances lets an implementation reconstruct the discovered path later.

python
from collections import deque

def distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph.get(u, []):
            if v not in distance:
                distance[v] = distance[u] + 1
                queue.append(v)
    return distance

DFS explores a branch and returns

Depth-first search follows a branch deeply before returning to alternatives. It can use an explicit stack or recursion. It is useful for reachability and structural analysis, but the first discovered path need not have the fewest edges. Omitting visited-state management can cause repeated traversal around a cycle.

A recursive implementation must also consider call-stack limits on deep graphs. For directed-cycle detection, distinguishing a vertex on the current exploration path from one completed earlier can be essential. The state needed by an algorithm depends on the property being tested, not just on whether the code is called DFS.

Weights and representations change the problem

Let A→B cost five, A→C cost one, and C→B cost one. A one-edge route reaches B, but the two-edge route through C costs only two. BFS minimizes edge count under equal-cost assumptions, not arbitrary weight sums. Consider Dijkstra for nonnegative weights and a suitable alternative when negative weights are allowed.

Basic BFS and DFS with adjacency lists can be analyzed in O(V+E) by accounting for vertex and edge work. An implementation repeatedly scanning rows of an adjacency matrix has a different cost. Check representation, reachable input, and auxiliary memory before transferring a complexity claim to particular code.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path