Graph Traversal Algorithms — How to Invent BFS, DFS & Dijkstra from Scratch

If you start from the problem "visit every vertex of a graph" without knowing BFS, DFS, or Dijkstra, the three algorithms come together in this order. First, keep a record of visited vertices (visited) so that cycles don't make you loop forever. Next, process the vertices you find nearest-first with a queue and you get BFS; process them deepest-first with a stack and you get DFS. When edges have weights, replace the queue with a priority queue ordered by distance and you get Dijkstra's algorithm.

Once you see why each data structure is needed, you don't need to memorize the steps: the same reasoning rebuilds them.

Start With the Problem

Before thinking about algorithms, decide what you want to solve.

The Fundamental Question: "Visit Every Place"

Imagine you're dropped into an unfamiliar city. You have no map, but you can see which roads lead away from where you are. How should you walk to visit every location without missing any?

This is the graph traversal problem.

To abstract the city, call intersections vertices and roads edges. The collection of vertices and edges is a graph.

Graph G = (V, E)
  V: set of vertices {A, B, C, D}
  E: set of edges    {(A,B), (A,C), (B,C), (B,D), (C,D)}

Many real-world problems can be modeled as graphs:

• Road networks: intersections are vertices, roads are edges
• Social networks: users are vertices, friendships are edges
• The Web: pages are vertices, hyperlinks are edges
• Dependencies: packages are vertices, dependencies are edges

When edges have direction, we get a directed graph (one-way streets). When edges have costs (distances, travel times), we get a weighted graph. In both cases, the basic move of traversal is the same: follow an edge from a vertex to a neighbor.

Graph Representation: Build the "Who Are My Neighbors?" Machinery

Next, decide how to represent a graph in code. Here too, we work backwards from the operations we need.

The most frequent operation in traversal is listing all neighbors of a given vertex, so we choose a representation that makes this fast.

Adjacency List — "Who are this person's friends?"

Store a list of neighbors for each vertex. This suits sparse graphs (graphs with few edges).

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

Space is $O(V + E)$, and listing neighbors takes $O(\text{degree})$. All the traversal algorithms in this article assume an adjacency list.

Adjacency Matrix — "Are these two people friends?"

Build a $V \times V$ table and set 1 where an edge exists. You can check whether an edge exists between two specific vertices in $O(1)$, but the table needs $O(V^2)$ space.

#     A  B  C  D
matrix = [
    [0, 1, 1, 0],  # A
    [1, 0, 1, 1],  # B
    [1, 1, 0, 1],  # C
    [0, 1, 1, 0],  # D
]

Thought Experiment 1: The Most Naive Traversal

Given a graph, how do we visit every vertex?

The First Wall: "I Keep Revisiting the Same Place"

The first idea is "if you can go to a neighbor, go." But unlike trees, graphs can have cycles (loops). A→B→C→A→B→… and you loop forever.

So we keep a visited record to avoid visiting the same vertex twice.

visited = set()  # Without this, we loop forever

This visited record appears in all three algorithms in this article (in Dijkstra, the distance table dist plays that role). Because graphs can have cycles, some form of it is always needed.

The Next Question: "When I Have Multiple Unvisited Neighbors, Which Do I Visit First?"

You're at vertex A with two unvisited neighbors, B and C. Which one you visit first, and when you visit the vertices you find beyond them, splits the approach into two strategies.

The BFS Insight — "Before Going Far, Check Everything Nearby"

Reframe the Problem: "Where's the Nearest Convenience Store?"

If you were looking for the nearest convenience store in an unfamiliar city, you wouldn't charge down a single street forever. You'd check all the blocks right around you first, then the ring outside them, spreading outward in concentric circles.

BFS (Breadth-First Search) does this on a graph:

If I check nearby places first, then whatever I find is guaranteed to be the closest.

The Design Core: Use a "Waiting Line"

To see how to implement "process nearby vertices first," trace it from starting vertex A:

1. Add A's neighbors B and C to a "to-do list"
2. Process B. Add B's neighbors D and E to the "to-do list"
3. Don't process D or E yet; process C first

C goes first because it entered the list before D and E. C is at distance 1 from the start, while D and E are at distance 2. In BFS, a vertex discovered earlier is closer to the start, so a queue (FIFO: first in, first out) processes vertices nearest-first.

Why a Queue Guarantees Shortest Paths

Because of FIFO order, all vertices at distance $d$ are processed before any vertex at distance $d+1$.

We can check this by induction:

1. The source (distance 0) is processed first ✓
2. When a distance-$d$ vertex is processed, its undiscovered neighbors (distance $d+1$) are enqueued
3. FIFO ensures all distance-$d$ vertices are processed before distance-$d+1$ vertices
4. If vertex $v$ is first discovered at distance $d$ and a shorter path existed, $v$ would already have been discovered at an earlier level, which is a contradiction

Formally, the following invariant always holds: the distances of the vertices in the queue are non-decreasing from front to back, and the front and back differ by at most 1.

The Algorithm

In code:

from collections import deque
 
def bfs(graph, start):
    visited = set()        # Insight 1: don't revisit vertices
    queue = deque([start]) # Insight 2: queue ensures "nearest first"
    visited.add(start)
    order = []
 
    while queue:
        vertex = queue.popleft()  # First in, first out (FIFO)
        order.append(vertex)
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)   # Mark visited when enqueuing
                queue.append(neighbor)
 
    return order

visited.add(neighbor) is called at enqueue time, not dequeue time. If we waited until dequeue and both B and C were neighbors of D, D would be enqueued twice: once while processing B and once while processing C. Marking a vertex the moment it is discovered prevents this double enqueue.

Step Through It

The visualizer below shows BFS in action:

• The queue always holds vertices in order of distance from the start
• All distance-1 vertices are processed before any distance-2 vertex
• The visited region spreads out from the start like a ripple

BFS Complexity

• Time: $O(V + E)$ — each vertex enters the queue once, and each adjacency-list entry is examined once
• Space: $O(V)$ — queue and visited set

The DFS Insight — "Go All the Way Down One Path First"

A Different Problem: "Is There an Exit?"

Now the question is not "what's nearest?" but "Does this maze have an exit? Can I explore every room?"

People walking through a maze usually do this:

1. At a fork, pick one path and walk as far as possible
2. At a dead end, go back to the last fork
3. Try a different path, again going as far as possible
4. Repeat until every path has been tried

Ignore whether a path is shortest and explore every path without missing any: that's DFS (Depth-First Search).

The Design Core: Recursion as a Natural Structure

This strategy can be written directly as recursion.

At vertex $v$, we explore all of $v$'s neighbors. Exploring a neighbor $u$ means exploring all of $u$'s neighbors while at $u$. The same problem repeats one vertex further along:

explore(v):
  mark v as visited
  for each neighbor u of v:
    if u is unvisited, call explore(u)

This recursion goes as deep as it can and turns back at dead ends. When explore(u) returns, control goes back to explore(v); that return is the backtracking.

Why a "Stack"? — Recursion and the Call Stack

If you try to write DFS without recursion, you can see why it needs a stack.

In BFS, we put "vertices to process later" into a queue. DFS stores them too, but it wants to process the most recently added vertex, the deepest one, first. Taking out the last thing put in is what a stack (LIFO: last in, first out) does. A recursive call does the same thing internally with the call stack.

The central difference between BFS and DFS is which end the next vertex is taken from:

BFS: queue.popleft()  → first added (nearest) processed first
DFS: stack.pop()      → last added (deepest) processed first

Changing how vertices are taken out changes the traversal order, and with it the problems each traversal suits. (In the stack version below, the point at which a vertex is marked visited also differs from BFS.)

The Algorithm (Recursive)

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
 
    visited.add(start)
    print(start)  # Process vertex
 
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)  # Recurse = go deeper
 
    # Returning here = backtracking
    return visited

The Algorithm (Iterative with Stack)

When recursion depth is a concern:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
 
    while stack:
        vertex = stack.pop()  # Last in, first out (LIFO)
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
 
        for neighbor in reversed(graph[vertex]):
            if neighbor not in visited:
                stack.append(neighbor)
 
    return order

Step Through It

Switch the visualizer above to DFS mode to see how it differs from BFS:

• The call stack grows deeper in one direction
• Backtracking happens at dead ends
• The visit order differs from BFS and does not go nearest-first

Discovery and Finish Times — DFS's Bonus Information

DFS can record a discovery time (when each vertex was discovered) and a finish time (when its exploration finished). BFS doesn't give you this information.

time = 0
 
def dfs_with_timestamps(graph, vertex, visited, discovery, finish):
    global time
    time += 1
    discovery[vertex] = time  # Discovery time
    visited.add(vertex)
 
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_with_timestamps(graph, neighbor, visited, discovery, finish)
 
    time += 1
    finish[vertex] = time  # Finish time

On a directed acyclic graph (DAG), the reverse of DFS finish order is a topological sort. With the convention that an edge $u \to v$ means "$u$ must come before $v$," every edge in a DAG satisfies $\mathrm{finish}(u) > \mathrm{finish}(v)$, so reversing finish times puts $u$ before $v$. If the graph has a cycle, topological order does not exist, so DFS has to detect the cycle and report an error.

BFS and DFS Have the Same Complexity

• Time: $O(V + E)$
• Space: $O(V)$

Both process each vertex once and each adjacency-list entry once, so their complexity is the same. What differs is the processing order, and that difference decides which problems each one suits.

Comparing BFS and DFS Side by Side

Choosing Between Them — Read the Problem Structure

BFS when "distance" matters:

• Shortest path (unweighted graphs)
• All nodes within $k$ hops
• Bipartiteness testing (can we 2-color the graph?)

DFS when "structure" matters:

• Cycle detection (in directed graphs, did we encounter a vertex currently on the recursion stack? In undirected graphs, did we encounter a visited vertex other than the parent?)
• Topological sort (reverse finish times)
• Connected/strongly connected components
• Backtracking (puzzles, constraint satisfaction)

If you want to spread outward nearest-first, use BFS; if you want to follow one path to the end, use DFS.

Thought Experiment 2: Hitting BFS's Limitation

BFS finds shortest paths in unweighted graphs. What about this problem?

"What's the fastest route from Tokyo to Osaka?"

Each road has a different travel time (weight). Suppose a direct road from Tokyo to Osaka takes 5 hours, while going Tokyo→Nagoya→Osaka over two roads takes 4 hours in total.

BFS minimizes the number of edges (hops), so it picks the 1-edge direct route (5 hours). Because it ignores edge weights, it misses the 4-hour route over two edges. When edge costs aren't uniform, BFS can't guarantee the shortest distance.

So we look for a way to make BFS handle weights.

The Dijkstra Insight — Adapting BFS for Weights

Step 1: Re-analyze What BFS Was Guaranteeing

Recall why BFS works:

1. Finalize distance-0 vertices (just the source)
2. Finalize distance-1 vertices (all neighbors of the source)
3. Finalize distance-2 vertices (undiscovered neighbors of distance-1 vertices)
4. …

The queue's FIFO order guaranteed that smaller distances were finalized first.

In weighted graphs, being a neighbor doesn't mean being close. In the earlier example, the direct Tokyo–Osaka edge (5 hours) is longer than the 2-edge path through Nagoya (4 hours in total).

Step 2: "What If I Sort the Queue by Distance?"

So we order the queue by distance instead of insertion order, replacing the FIFO queue with a priority queue.

• BFS: queue (FIFO) → discovered earlier = fewer edges
• Dijkstra: priority queue → smaller total distance = less total weight

Dijkstra's algorithm is BFS with its queue replaced by a priority queue.

Step 3: "The Minimum-Distance Vertex Is Safe to Finalize"

Here is why the distance of the vertex $u$ at the front of the priority queue can be finalized:

The vertex $u$ at the front of the priority queue cannot be reached by any shorter path. Why? All unprocessed vertices have distance ≥ that of $u$, and since edge weights are non-negative, routing through them cannot reduce the distance.

This argument holds only when edge weights are non-negative. With negative edges, a detour through a "farther" vertex can reduce the total distance, and the argument breaks. For negative edges, use an algorithm such as Bellman-Ford.

Step 4: The "Relaxation" Operation

When we finalize vertex $u$ and look at a neighbor $v$, we update $v$'s distance if going through $u$ is shorter than what we currently have for $v$. This operation is called relaxation.

"Relaxation" is a historical term, usually explained as coming from the constraint $d(v) \le d(u) + w(u, v)$. What the operation actually does is lower a distance estimate (an upper bound) that starts at $\infty$ each time a better path is found.

Putting the Reasoning Into Code

import heapq
 
def dijkstra(graph, start):
    # graph: { node: [(neighbor, weight), ...] }
    dist = {node: float('inf') for node in graph}  # Start at infinity
    prev = {node: None for node in graph}
    dist[start] = 0                                 # Source is 0
    pq = [(0, start)]  # Priority queue (replaces BFS's queue)
 
    while pq:
        d, u = heapq.heappop(pq)  # Extract minimum distance (replaces popleft)
 
        if d > dist[u]:  # Skip stale entries
            continue
 
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:  # Relaxation: better path found
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))
 
    return dist, prev

The structure is nearly the same as the BFS code. Three things changed:

1. Queue → priority queue (extract by distance, not insertion order)
2. visited → dist table (track distances, not just visited/unvisited)
3. Relaxation check added (new_dist < dist[v])

Step Through It

The visualizer below shows:

• A distance that was already set getting improved through a different path (that's relaxation)
• The minimum-distance vertex always being selected and finalized
• The prev column ending up as the shortest path tree

Dijkstra's Complexity

It depends on the data structure:

• Binary heap: $O((V + E) \log V)$. The most common choice
• Fibonacci heap: $O(V \log V + E)$. The smallest theoretical bound of the three, but complex to implement
• Array (naive loop): $O(V^2)$. Faster than a binary heap on dense graphs, where the number of edges approaches $V^2$

Tracing the Evolution of the Three Algorithms

Starting point: "I want to visit every vertex in a graph without missing any"

Insight 1 — visited: Cycles cause infinite loops, so we need a visited record

The fork — "In what order?":

• "Nearby places first" → FIFO queue → BFS
• "One path all the way to the end" → LIFO stack / recursion → DFS

Evolution — "What if edges have weights?":

• Replace BFS's queue with a priority queue → Dijkstra
• Key insight: "the minimum-distance vertex is safe to finalize" + relaxation

DFS came from a different question than BFS (explore every path), and Dijkstra came from BFS's inability to handle weights. Both began by identifying what about the previous approach didn't fit a new question or condition.

Applications: How the Insights Transfer

Topological Sort — A Byproduct of DFS

When a build system has "libA depends on libB" and "libB depends on libC," determining build order is topological sort.

For a DAG, the reverse of DFS finish order gives the build order. With edges directed from dependency to dependent, the libraries form "libC → libB → libA," and the reverse finish order gives the build order C → B → A. If a cycle is found, no topological order exists.

def topological_sort(graph):
    visited = set()
    result = []
 
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)  # Add on completion
 
    for node in graph:
        if node not in visited:
            dfs(node)
 
    return result[::-1]  # Reverse = topological order

Bipartiteness Testing — Exploiting BFS's Layer Structure

The problem is to decide whether a graph's vertices can be colored with 2 colors so that no adjacent vertices share a color. Using BFS's level-by-level processing, alternate colors between even and odd levels:

def is_bipartite(graph):
    color = {}
    for start in graph:
        if start in color:
            continue
        queue = deque([start])
        color[start] = 0
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False  # Same-color neighbors = not bipartite
    return True

Complexity Summary

Conclusion — The Steps That Led to All Three Algorithms

All three algorithms came from the same steps:

1. Define the problem: Decide what you want to find
2. Try the naive approach: Start with the simplest method and see where it fails
3. Identify the bottleneck: Looping on cycles → visited; visiting order → choice of data structure
4. Solve with data structures: Whether you use a queue, a stack, or a priority queue determines the strategy
5. Verify correctness: Check why it works and under what conditions it breaks (Dijkstra and negative edges)

Use a queue to process nearest-first, a stack to go deep first, and a priority queue to account for weights. BFS, DFS, and Dijkstra each follow from one of these. For a problem that isn't in any textbook, following the same five steps gives you a good idea of which data structure to reach for.