DevPath
Tracks

Graphs: Representations, BFS and DFS

Model networks as vertices and edges, choose between adjacency lists and matrices, and explore with breadth-first and depth-first search.

intermediate50 min#graphs#bfs#dfs#adjacency-list#traversal

Prerequisites: Trees and Binary Search Trees, Stacks and Queues, Hash Tables

Why it matters

Graphs describe relationships: roads between cities, friends in a social network, links between web pages, dependencies between packages, states in a game. A huge share of real problems become easy once you notice they are graph problems in disguise, and a tree is simply a graph with no cycles. Two traversals, BFS and DFS, are the foundation for nearly every graph algorithm that follows.

Intuition

A graph is a set of vertices (nodes) joined by edges. Edges can be undirected (friendship) or directed (follows), and may carry a weight (distance, cost). A path is a sequence of edges, a cycle is a path that returns to its start, and a graph is connected if every vertex can reach every other.

Exploring a maze gives the two traversals. DFS is the strategy of one person with a ball of string: go as deep as possible down one corridor, and back up only at a dead end. BFS is a crowd spreading out: everyone takes one step, then everyone takes one more, so you reach all places one step away before any place two steps away. That layering is why BFS finds the shortest path when all edges count equally.

   A --- B
   |     |
   C --- D --- E

 BFS from A:  A | B C | D | E      (layers 0, 1, 1, 2, 3)
 DFS from A:  A B D C E            (dives before backing up)
ABCDE
The undirected graph used throughout this lesson (the same one drawn above and used in the code). A line works in both directions, so A-B means A knows B and B knows A.
ABCD
A directed graph (think of who follows whom). Arrows have a direction: A reaches B, but B does not reach A directly. A to B to C to A is a cycle, and D can be reached from C but leads nowhere.

How it works

Representations. Let V be the number of vertices and E the number of edges.

  • Adjacency list: for each vertex, a list of its neighbors. Space is O(V + E). Iterating the neighbors of a vertex is proportional to its degree. This is the default, because most real graphs are sparse (E is far smaller than V squared).
  • Adjacency matrix: a V by V grid where cell [u][v] is 1 (or the weight) if the edge exists. Space is O(V squared). Checking whether an edge exists is O(1), but listing neighbors costs O(V). Use it for small or dense graphs.
  • Edge list: just a list of pairs. Simple for sorting edges (Kruskal's algorithm) but slow for neighbor queries.

For an undirected graph, store each edge in both directions. For a directed graph, store it once.

Here is the five-vertex graph from the code in both forms.

ABCDE
A
0
1
1
0
0
B
1
0
0
1
0
C
1
0
0
1
0
D
0
1
1
0
1
E
0
0
0
1
0
Adjacency matrix: cell [row][col] is 1 if the edge exists. It is symmetric because the graph is undirected, and most cells are 0 (wasted space on sparse graphs). The highlighted row is D, the same row the code prints.
B, C
A
A, D
B
A, D
C
B, C, E
D
D
E
Adjacency list for the same graph: one short list of neighbors per vertex, and only existing edges take space. The highlighted entry says D touches B, C and E, so listing neighbors costs only the degree.

The visited set. Unlike a tree, a graph can contain cycles, so a traversal must remember what it has seen or it will loop forever. Mark a vertex as seen when you enqueue or push it, not when you pop it, otherwise the same vertex can be queued many times.

BFS uses a queue. Pop a vertex, push each unseen neighbor and record its distance as one more than the current vertex. Each vertex and edge is processed once: O(V + E). The recorded distances are shortest-path lengths in an unweighted graph.

ABCDE
BFS from A. Queue: [A]. Seen: A (distance 0). A is marked when it is enqueued.
step 1 / 6

BFS from A. Green is the vertex just popped, amber vertices are waiting in the queue, and highlighted edges show how each vertex was first discovered. The layers are the distances: 0, then B and C at 1, D at 2, E at 3.

DFS uses a stack, either explicitly or through recursion. Visit a vertex, then recurse into each unseen neighbor. Also O(V + E). DFS is the tool for reachability, finding connected components, detecting cycles, and topological sorting.

ABCDE
DFS from A (recursive). Call stack: [A]. Visit A.
step 1 / 7

DFS from A. Green is the current vertex, amber vertices are on the recursion stack (still waiting to try their other neighbors), highlighted edges are the ones followed. DFS goes as deep as it can before backing up.

OperationTimeNotes
BFS / DFS (adjacency list)O(V + E)Each vertex and edge once
BFS / DFS (adjacency matrix)O(V squared)Row scan per vertex
Edge exists? (list / matrix)O(degree) / O(1)Matrix wins for lookups
List neighbors (list / matrix)O(degree) / O(V)List wins for sparse graphs
Space (list / matrix)O(V + E) / O(V squared)Matrix wasteful when sparse

Code: BFS, DFS and reachability

import json
from collections import deque
 
def show(*xs):
    print(*(json.dumps(x, separators=(',', ':')) for x in xs))
 
edges = [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D"), ("D", "E")]
graph = {}
for u, v in edges:  # undirected: store both directions
    graph.setdefault(u, []).append(v)
    graph.setdefault(v, []).append(u)
 
def bfs(graph, start):
    """Visit order and shortest distance (in edges) from start."""
    dist = {start: 0}
    order = []
    q = deque([start])
    while q:
        u = q.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return order, dist
 
def dfs(graph, u, seen=None):
    seen = set() if seen is None else seen
    seen.add(u)
    order = [u]
    for v in graph[u]:
        if v not in seen:
            order += dfs(graph, v, seen)
    return order
 
def has_path(graph, src, dst):
    seen, stack = {src}, [src]
    while stack:
        u = stack.pop()
        if u == dst:
            return True
        for v in graph.get(u, []):
            if v not in seen:
                seen.add(v)
                stack.append(v)
    return False
 
show(bfs(graph, "A")[0])
show(bfs(graph, "A")[1])
show(dfs(graph, "A"))
graph["X"] = ["Y"]
graph["Y"] = ["X"]
show(has_path(graph, "A", "E"), has_path(graph, "A", "Y"))
 
# adjacency matrix for the first five nodes
names = ["A", "B", "C", "D", "E"]
idx = {n: i for i, n in enumerate(names)}
m = [[0] * 5 for _ in range(5)]
for u, v in edges:
    m[idx[u]][idx[v]] = m[idx[v]][idx[u]] = 1
show(m[idx["D"]])

Both versions print:

["A","B","C","D","E"]
{"A":0,"B":1,"C":1,"D":2,"E":3}
["A","B","D","C","E"]
true false
[0,1,1,0,1]

BFS visits A, then its neighbors B and C, then D, then E, and reports their distances. DFS dives A, B, D, then backs up to C before E. The vertices X and Y form a separate component, so there is no path from A to Y. The last line is row D of the adjacency matrix: D is connected to B, C and E.

Common pitfalls

  • No visited set: any graph with a cycle (including every undirected edge, which is a two-step cycle) will loop forever.
  • Marking visited too late: marking on pop lets a vertex enter the queue repeatedly, which can blow up the running time.
  • Using list.pop(0) or shift() as the queue: each call is O(n). Use collections.deque in Python, and a head index (as above) in JavaScript.
  • Forgetting disconnected graphs: one traversal from one start only reaches one component. Loop over all vertices to cover everything.
  • Recursion limits: DFS on a path of 100,000 vertices overflows the default stack in Python and JavaScript. Convert to an explicit stack.
  • Undirected edge stored once: the neighbor lookup then fails in one direction.

Practice

Does a path exist? easy

Hint

Any traversal from the source works. What do you check when you pop a vertex?

Show solution

Run BFS or DFS from the source with a visited set and return true as soon as you reach the destination, false if the traversal ends first. O(V + E).

Number of islands medium

Hint

Treat each land cell as a vertex and loop over every cell as a possible start.

Show solution

Scan the grid. When you find an unvisited land cell, increment the count and flood-fill (DFS or BFS) over its land neighbors, marking them visited. Each cell is processed once, O(rows times columns).

Shortest path in a binary maze medium

Hint

Which traversal discovers vertices in order of distance?

Show solution

BFS from the start cell, storing the distance with each queued cell and stopping at the goal. Because every step has the same cost, the first time BFS reaches a cell is via a shortest path. DFS cannot promise that.

Clone a graph hard

Hint

You need a map from each original node to its copy, which doubles as the visited set.

Show solution

Traverse with BFS or DFS. When you meet an original node, create its copy if it is not yet in the map. For each neighbor, ensure a copy exists and append it to the copy's neighbor list. The map prevents infinite loops on cycles. O(V + E).

Interview questions

  1. Adjacency list or matrix? The list for sparse graphs (the common case): O(V + E) space. The matrix for dense graphs or when you need O(1) edge lookup.
  2. When is BFS better than DFS? For shortest paths in unweighted graphs and level-by-level processing. DFS suits exhaustive exploration, cycles, components and topological order.
  3. What is the complexity of BFS? O(V + E) with an adjacency list.
  4. How do you handle a graph with cycles? Keep a visited set, marked when a vertex is first discovered.
  5. How is a tree different from a graph? A tree is a connected graph with no cycles and exactly V minus 1 edges.

Interviewers look for: asking whether the graph is directed, weighted, or possibly disconnected, choosing a representation with a reason, and marking visited at the right moment.

Quick check

You need the fewest number of edges between two people in a social network where every connection counts the same. Which approach fits?

Finished this lesson?

Further resources

Related lessons