-
Notifications
You must be signed in to change notification settings - Fork 0
011 — Graphs
Trees have been the shape of everything so far — one root, no cycles, every node reachable exactly one way. A graph drops all three of those guarantees. It's the most general "things connected to other things" structure in this wiki, and every tree you've seen is secretly a special case of one.
Picture a subway map. Stations are dots, tracks between them are lines. There's no single "root station" everything branches from — you can start anywhere. Some stations connect to three or four others; some are dead ends. Critically, you can often get from station A to station B by more than one route, and sometimes you can ride in a loop and end up back where you started.
- 🚉 Each station is a vertex (or node).
- 🛤️ Each track between two stations is an edge.
- 🔁 Unlike a tree, there's no rule against cycles — the Circle Line is, by design, a loop.
↔️ Some lines only run one direction (a one-way street, a "follows" relationship on social media) — that's a directed graph. Subway tracks usually run both ways — that's undirected.
A tree is just a graph that happens to have no cycles and exactly one path between any two nodes. A graph makes no such promise — which is exactly why it needs its own toolkit for asking "can I get from A to B at all," and if so, "what's the shortest way."
A graph is a set of vertices connected by edges. Two independent axes describe any graph you'll encounter:
-
Directed vs. undirected — does an edge
A → BimplyB → Afor free, or not? - Weighted vs. unweighted — does each edge carry a cost/distance, or are all edges "equal"?
The two standard ways to represent a graph in code:
- Adjacency list — a dictionary (or array) mapping each vertex to the list of vertices it connects to directly. Compact, and the one used almost everywhere in interviews.
-
Adjacency matrix — an
n × ngrid wherematrix[i][j]istrue(or a weight) if an edge exists fromitoj. Simple, but wastes space on sparse graphs (few edges relative to vertices) since most cells are empty.
Swift has no stdlib graph type — hand-rolled, almost always as an adjacency list, since it's what most interview problems expect.
The two traversal algorithms every graph problem builds on:
-
BFS (breadth-first search) — explore layer by layer using a queue (Chapter 06). Finds the shortest path in an unweighted graph, because it never explores a node at distance
k+1before every node at distancek. - DFS (depth-first search) — explore as deep as possible before backtracking, using a stack (explicit, or the call stack via recursion, Chapter 05). Natural for "does a path exist," cycle detection, and problems that need to explore every possibility (backtracking).
Reach for a graph when:
- Your data is a network of relationships that isn't strictly hierarchical — friend networks, road maps, dependency graphs, course prerequisites.
- You need shortest path (BFS for unweighted, Dijkstra's — a heap-driven BFS variant, Chapter 09 — for weighted), or you need to detect a cycle (common in "can these tasks be scheduled" problems).
- The problem says "connections," "network," "can you reach," or gives you a list of pairs describing relationships — that's almost always a graph in disguise, even when the word "graph" never appears.
Skip it when your data actually has a strict single-parent hierarchy — that's a tree, and tree algorithms (Chapter 07) are simpler and often faster than treating it as a general graph.
An undirected graph with a cycle — something a tree could never represent:
1 ─────── 2
│ │
│ │
3 ─────── 4 ─────── 5
adjacency list:
1: [2, 3]
2: [1, 4]
3: [1, 4]
4: [2, 3, 5]
5: [4]
Note the cycle: 1 → 2 → 4 → 3 → 1. There are TWO distinct paths
from 1 to 4 (via 2, or via 3) — a tree guarantees exactly one path
between any two nodes; a graph makes no such promise.
No stdlib equivalent — adjacency list, generic over any Hashable vertex type, with both BFS and DFS.
struct Graph<T: Hashable> {
private(set) var adjacency: [T: [T]] = [:]
mutating func addVertex(_ vertex: T) {
if adjacency[vertex] == nil {
adjacency[vertex] = []
}
}
mutating func addEdge(_ from: T, _ to: T, bidirectional: Bool = true) {
addVertex(from)
addVertex(to)
adjacency[from]?.append(to)
if bidirectional {
adjacency[to]?.append(from)
}
}
// BFS: layer by layer, using a queue — guarantees shortest path in an
// unweighted graph, because every node at distance k is visited before
// any node at distance k+1.
func bfs(from start: T) -> [T] {
guard adjacency[start] != nil else { return [] }
var visited: Set<T> = [start]
var queue: [T] = [start]
var order: [T] = []
var head = 0 // index-based "dequeue" avoids O(n) removeFirst() — see Chapter 06
while head < queue.count {
let current = queue[head]
head += 1
order.append(current)
for neighbor in adjacency[current] ?? [] where !visited.contains(neighbor) {
visited.insert(neighbor)
queue.append(neighbor)
}
}
return order
}
// DFS: as deep as possible before backtracking, using the call stack.
func dfs(from start: T) -> [T] {
var visited: Set<T> = []
var order: [T] = []
dfsVisit(start, &visited, &order)
return order
}
private func dfsVisit(_ vertex: T, _ visited: inout Set<T>, _ order: inout [T]) {
guard !visited.contains(vertex) else { return }
visited.insert(vertex)
order.append(vertex)
for neighbor in adjacency[vertex] ?? [] {
dfsVisit(neighbor, &visited, &order)
}
}
}Usage:
var graph = Graph<Int>()
graph.addEdge(1, 2)
graph.addEdge(1, 3)
graph.addEdge(2, 4)
graph.addEdge(3, 4)
graph.bfs(from: 1) // [1, 2, 3, 4] — visits both neighbors of 1 before going deeper
graph.dfs(from: 1) // [1, 2, 4, 3] — commits to the 2-branch fully before backtracking to 3In both traversals, the visited set is what keeps a graph traversal from looping forever around a cycle — a tree traversal never needs one, because a tree has no cycles to loop on.
Let V be the number of vertices and E be the number of edges.
| Operation | Big-O | Why |
|---|---|---|
| BFS / DFS traversal | O(V + E) |
Every vertex is visited once (V), and every edge is examined once when scanning that vertex's neighbor list (E) — this is the single most important complexity to memorize in this chapter. See Big-O Notation. |
| Add edge (adjacency list) | O(1) |
Just an array append on both sides (if bidirectional). |
| Check if edge exists (adjacency list) | O(degree of vertex) |
Must scan that vertex's neighbor list — no shortcut without an auxiliary set. |
| Check if edge exists (adjacency matrix) | O(1) |
Direct index into matrix[i][j] — the one place a matrix beats a list. |
| Space — adjacency list | O(V + E) |
One entry per vertex, plus one entry per edge (two, if undirected — each side lists the other). |
| Space — adjacency matrix | O(V²) |
Fixed grid size regardless of how many edges actually exist — wasteful for a sparse graph, reasonable for a dense one. |
A graph is a subway map, not a family tree — no single root, connections in every direction, and sometimes a loop that brings you right back to where you started.
For the graph in the ASCII diagram above (vertices 1-5, edges as shown), trace through bfs(from: 1) by hand — write out the queue and visited set after each iteration of the while loop. Then explain: why does BFS guarantee the shortest path in an unweighted graph, and give a concrete reason why that same guarantee breaks if the edges have different weights (e.g. edge 1-2 costs 10, but the two-hop path 1-3-2 costs only 2 total).