Data Structures: Graphs — Modeling the World as Nodes and Edges

Post #5’s trees restrict every node to exactly one parent — an accurate model for file systems and the DOM, but not for a social network (a friendship connects two people symmetrically, with no “parent”), a road map (a city connects to several others, with no hierarchy), or a set of software dependencies (a package can depend on several others, and be depended on by several more). A graph removes the one-parent restriction entirely, allowing any node to connect to any other, in any pattern — the most general, most flexible data structure in this series, and the one underneath an enormous share of real-world software.

---

Graph Fundamentals: Vertices and Edges

A graph consists of vertices (also called nodes — the same term used throughout Post #5) and edges, which connect pairs of vertices.

Directed vs. undirected: An undirected edge represents a mutual, symmetric relationship — a Facebook friendship, a road connecting two cities in both directions. A directed edge points one way only — a Twitter/X follow (following someone does not mean they follow you back), a one-way street, a package depending on another package.

Weighted vs. unweighted: A weighted edge carries an associated number — the distance between two cities, the cost of a network connection. An unweighted edge simply represents “connected” or “not connected,” with no additional value attached.

---

Representing Graphs in Code

Adjacency List

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

Each key maps to a list of the vertices it directly connects to — genuinely efficient for graphs where each vertex connects to relatively few others (called “sparse” graphs), which describes the large majority of real-world graphs (a person has friends numbering in the hundreds, not millions; a webpage links to dozens of other pages, not every page on the internet).

Adjacency Matrix

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

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0],
]

A 2D grid where matrix[i][j] = 1 indicates a connection between vertex i and vertex j. This makes checking “are these two specific vertices connected” genuinely instant (a single array lookup, directly using Post #3’s array coverage), but wastes considerable memory for sparse graphs — a matrix representing a million vertices with only a handful of connections each still allocates a million-by-million grid, overwhelmingly filled with zeros.

The practical guidance: adjacency lists are the more common real-world choice, specifically because most genuine real-world graphs are sparse.

---

Traversal: Breadth-First Search (Using a Queue)

BFS explores level by level — visiting every immediate neighbor before moving on to neighbors-of-neighbors, using exactly the queue covered in Post #3.

from collections import deque

def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []

    while queue:
        vertex = queue.popleft()  # FIFO — exactly Post #3's queue behavior
        order.append(vertex)
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

    return order


graph = {
    "A": ["B", "C"],
    "B": ["A", "D"],
    "C": ["A", "D"],
    "D": ["B", "C"],
}
print(bfs(graph, "A"))  # ['A', 'B', 'C', 'D']

This is precisely the same level-order traversal technique covered for trees in Post #5, generalized directly to graphs — the queue’s FIFO ordering naturally produces a breadth-first, level-by-level exploration pattern.

---

Traversal: Depth-First Search (Using a Stack, or Recursion)

DFS explores as deep as possible down one path before backtracking, using either an explicit stack (Post #3) or recursion (which uses the call stack, also covered in Post #3).

def dfs_recursive(graph, vertex, visited=None, order=None):
    if visited is None:
        visited = set()
        order = []
    visited.add(vertex)
    order.append(vertex)
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited, order)
    return order


print(dfs_recursive(graph, "A"))  # ['A', 'B', 'D', 'C']

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []

    while stack:
        vertex = stack.pop()  # LIFO — exactly Post #3's stack behavior
        if vertex not in visited:
            visited.add(vertex)
            order.append(vertex)
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    stack.append(neighbor)

    return order

The direct payoff worth noticing explicitly: BFS and DFS are, structurally, the exact same traversal algorithm, differing only in whether the “next vertex to visit” collection is a queue (BFS, FIFO, explore breadth-first) or a stack (DFS, LIFO, explore depth-first) — a genuinely elegant, concrete confirmation that Post #3’s coverage of stacks and queues was not abstract theory, but the literal mechanism determining two of the most important algorithms in this entire series.

---

Real-World Use Cases

Social networks: Friend/follower relationships are naturally modeled as a graph — “friends of friends” recommendations are a direct application of BFS, exploring outward level by level from a starting person.

Maps and navigation: Roads connecting locations form a weighted graph, with pathfinding algorithms (a more sophisticated relative of the BFS/DFS covered in this post) finding the shortest or fastest route between two points.

Dependency resolution: Software package dependencies, build systems, and task scheduling with prerequisites are all naturally modeled as directed graphs — determining a valid installation or execution order is a direct graph algorithm application (called topological sorting, beyond this introductory post’s scope but worth knowing exists).

Recommendation systems: “Users who liked this also liked…” recommendations frequently rely on graph structures connecting users and items, with traversal-based algorithms identifying relevant connections.

Web crawling: Search engines discovering pages by following links from page to page are performing graph traversal directly — every link is an edge, every page a vertex.

---

Common Mistakes and Gotchas

⚠️ Mistake 1: Forgetting to track visited nodes, causing infinite loops

def bad_dfs(graph, vertex):
    for neighbor in graph[vertex]:
        bad_dfs(graph, neighbor)  # BUG — no visited tracking, loops forever on any cycle!

Unlike Post #5’s trees, graphs can contain cycles — a path that loops back to an already-visited vertex — and without explicitly tracking visited nodes, exactly as every correct example in this post does, traversal can loop indefinitely.

⚠️ Mistake 2: Choosing an adjacency matrix for a genuinely sparse graph Covered above — this wastes substantial memory for real-world graphs where most vertices connect to only a small handful of others, which describes the overwhelming majority of practical graph applications.

⚠️ Mistake 3: Using BFS when DFS was the better fit, or vice versa BFS is naturally suited to “shortest path in an unweighted graph” and “explore nearby connections first” tasks; DFS is naturally suited to “does a path exist at all” and “explore one branch completely before considering alternatives” tasks — picking the wrong one produces a correct but needlessly inefficient or awkward solution for the specific problem.

⚠️ Mistake 4: Forgetting that a directed graph’s edges are not automatically bidirectional

graph = {"A": ["B"], "B": []}  # A follows B, but B does NOT follow A

Assuming a directed edge implies its reverse also exists is a genuine, common source of bugs when modeling real directed relationships like follows, dependencies, or one-way references.

---

Quick Reference

# Adjacency list (most common for sparse real-world graphs)
graph = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}

# BFS — queue, level-by-level, shortest path in unweighted graphs
from collections import deque
def bfs(graph, start):
    visited, queue, order = {start}, deque([start]), []
    while queue:
        v = queue.popleft()
        order.append(v)
        for n in graph[v]:
            if n not in visited:
                visited.add(n)
                queue.append(n)
    return order

# DFS — stack (or recursion), depth-first, explore one path fully first
def dfs(graph, start):
    visited, stack, order = set(), [start], []
    while stack:
        v = stack.pop()
        if v not in visited:
            visited.add(v)
            order.append(v)
            stack.extend(graph[v])
    return order

Representation	Space	Check if edge exists	Best For
Adjacency List	O(V + E)	O(degree of vertex)	Sparse graphs (most real-world cases)
Adjacency Matrix	O(V²)	O(1)	Dense graphs, frequent edge checks

---

Exercises

Exercise 1 — Direct application Using the bfs function from this post, write a function shortest_path_length(graph, start, end) that returns the number of edges in the shortest path between two vertices in an unweighted graph.

Exercise 2 — Slight variation Write a function has_path(graph, start, end) -> bool using DFS that determines whether any path exists at all between two vertices, without needing to find the shortest one.

Exercise 3 — Real-world combination Model a small set of software package dependencies as a directed graph (e.g., {"app": ["auth", "database"], "auth": ["database"], "database": []}), and use DFS to determine a valid installation order — installing each package’s dependencies before the package itself.

Exercise 4 — Open-ended challenge Deliberately construct a graph containing a cycle, run the buggy bad_dfs pattern shown in this post’s mistakes section against it (in a safe, limited way — perhaps with a maximum iteration count to avoid an actual infinite loop), and confirm it fails to terminate the way a correctly visited-tracking version does.

---

FAQ

Q: Is a tree a special kind of graph? A: Yes — a tree is specifically a connected, acyclic (no cycles) graph with exactly one path between any two vertices; every tree is a graph, but not every graph is a tree, since graphs generally permit cycles and multiple paths between vertices that trees explicitly do not.

Q: Which is generally faster, BFS or DFS? A: Neither is inherently faster in the general case — both visit every reachable vertex exactly once, giving both the same overall time complexity; the right choice depends on what you are actually trying to find, covered directly in this post’s common mistakes section.

Q: Do I need to implement graph algorithms from scratch in real projects? A: Rarely for the core traversal algorithms covered in this post — most languages have well-established graph libraries, and many real-world graph problems (routing, dependency resolution) are handled by specialized, heavily optimized existing tools. Understanding the underlying mechanism remains valuable for reasoning correctly about what those tools are actually doing.

Q: What’s the difference between a “weighted shortest path” and what BFS finds? A: BFS finds the shortest path by number of edges (hops) in an unweighted graph — for a weighted graph, where edges have different costs, a different algorithm (commonly Dijkstra’s algorithm) is needed to account for those weights, genuinely beyond this introductory post’s scope but worth knowing exists as the next step beyond BFS.

---

Summary and Next Steps

You now understand graphs as the most general, flexible structure in this series — any node connecting to any other, directed or undirected, weighted or unweighted — and, genuinely satisfyingly, that BFS and DFS are the exact same underlying traversal algorithm, differing only in whether Post #3’s queue or stack drives the exploration order. This connects directly back to that earlier post, confirming those structures were never abstract theory disconnected from real algorithmic use.

Your next step: Complete Exercise 3 — modeling package dependencies and finding a valid install order via DFS — since this is one of the most immediately, practically recognizable real-world applications of everything this post has covered, directly relevant to any software project with genuine dependencies.

This concludes Module 2 of this series — every foundational data structure (arrays, linked lists, stacks, queues, hash tables, trees, and graphs) is now covered. The next module turns to algorithms: precisely measuring and comparing how efficiently code actually runs, starting with the notation that makes “efficient” a rigorous, comparable claim rather than a vague impression.

---

Last updated: August 2026.