Difficulty: Advanced | Prerequisites: Trees, heaps, disjoint sets, Big-O analysis, queues and stacks
Graphs are the most general data structure in the course. Trees are graphs; linked lists are graphs; social networks, road maps, and the internet are all graphs. This section covers how to represent them, how to traverse them, and how to solve two classic optimisation problems on them: minimum spanning trees and shortest paths. The algorithms here (BFS, DFS, Kruskal's, Prim's, Dijkstra's, Floyd-Warshall) are among the most important in computer science. You will use heaps, disjoint sets, stacks, and queues as sub-components, so make sure those foundations are solid.
TL;DR: Graphs are vertices connected by edges. You store them with adjacency lists or adjacency matrices. BFS and DFS explore the graph. Kruskal's and Prim's find minimum spanning trees. Dijkstra's finds shortest paths from one source; Floyd-Warshall finds shortest paths between all pairs.
Graph
A set of vertices (nodes) and edges (connections between nodes). In simple terms, dots connected by lines.
Directed graph (digraph)
A graph where edges have a direction: edge (u, v) goes from u to v but not necessarily from v to u.
Undirected graph
A graph where edges have no direction: edge {u, v} connects u and v in both directions.
Weighted graph
A graph where each edge carries a numerical value (weight, cost, distance).
Adjacency matrix
A V × V matrix where entry [i][j] is 1 (or the edge weight) if there is an edge from vertex i to vertex j, and 0 (or infinity) otherwise. Uses O(V²) space.
Adjacency list
For each vertex, store a list of its neighbours (and edge weights if applicable). Uses O(V + E) space. More efficient than a matrix when the graph is sparse.
Sparse graph
A graph with far fewer edges than the maximum possible. Roughly E = O(V). Adjacency lists are preferred.
Dense graph
A graph with edges close to the maximum V². Adjacency matrices become competitive.
Breadth-first search (BFS)
Explore all neighbours at the current depth before moving to the next depth level. Uses a queue. Finds the shortest path in an unweighted graph.
Depth-first search (DFS)
Explore as far as possible along each branch before backtracking. Uses a stack (or recursion). Useful for cycle detection, topological sort, and connected components.
Minimum spanning tree (MST)
A subset of edges that connects all vertices in an undirected, weighted graph with the minimum total edge weight and no cycles. A tree with V - 1 edges.
Kruskal's algorithm
Build the MST by sorting all edges by weight and adding them one by one, skipping any edge that would create a cycle. Uses disjoint sets for cycle detection.
Prim's algorithm
Build the MST by growing a single tree: start from any vertex, repeatedly add the cheapest edge connecting the tree to a vertex not yet in the tree. Uses a priority queue (min-heap).
Dijkstra's algorithm
Find the shortest path from a single source to all other vertices in a graph with non-negative edge weights. Uses a priority queue.
Floyd-Warshall algorithm
Find shortest paths between all pairs of vertices. Uses dynamic programming with O(V³) time and O(V²) space.
Shortest path
The path between two vertices with the minimum total edge weight (or fewest edges in an unweighted graph).
Adjacency matrix
O(V²) space regardless of edge count
O(1) edge lookup: is there an edge from u to v?
Iterating over all neighbours of a vertex: O(V)
Good for dense graphs
Adjacency list
O(V + E) space
Edge lookup: O(degree of u) in the worst case
Iterating over all neighbours: O(degree of u)
Good for sparse graphs and most practical applications
Edge list
Just a list of all edges
O(E) space
Useful for Kruskal's where you sort edges by weight
Poor for neighbour queries
BFS
Uses a queue and a visited set
Process: enqueue source, mark visited. Dequeue a vertex, process it, enqueue all unvisited neighbours.
Produces a BFS tree where the depth of each node equals its shortest-path distance (in edge count) from the source
Time: O(V + E)
DFS
Uses a stack (or recursion) and a visited set
Process: push source. Pop a vertex, if not visited mark it and push all unvisited neighbours.
Recursive version: visit node, recursively visit each unvisited neighbour
Useful for detecting cycles, finding connected components, topological sorting
Time: O(V + E)
Key difference: BFS finds the shortest path in unweighted graphs; DFS does not. DFS is more natural for problems involving exhaustive exploration or backtracking.
Properties of MSTs
A spanning tree of a connected graph with V vertices has exactly V - 1 edges
An MST is not necessarily unique (it is unique if all edge weights are distinct)
Cut property: for any cut of the graph, the lightest edge crossing the cut is in the MST
Kruskal's algorithm
Sort all edges by weight: O(E log E)
Initialise a disjoint set with each vertex in its own set
For each edge (u, v) in sorted order:
If find(u) ≠ find(v), add the edge to the MST and union(u, v)
Otherwise, skip it (would create a cycle)
Stop when V - 1 edges have been added
Total: O(E log E) dominated by the sort (since E log E ≈ E log V for simple graphs)
Prim's algorithm
Start with any vertex in the MST set
Insert all edges from that vertex into a min-priority queue
Extract the minimum-weight edge (u, v) where v is not yet in the MST
Add v to the MST, add all edges from v to non-MST vertices into the priority queue
Repeat until all vertices are in the MST
With a binary heap: O((V + E) log V)
With a Fibonacci heap: O(E + V log V)
When to use which
Kruskal's is simpler and works well for sparse graphs (sorting E edges is cheap when E is small)
Prim's with a good heap is better for dense graphs
Set distance to source = 0, distance to all others = infinity
Insert all vertices into a min-priority queue keyed by distance
Extract the vertex u with minimum distance
For each neighbour v of u: if distance[u] + weight(u, v) < distance[v], update distance[v] (relax the edge)
Repeat until the queue is empty
Time complexity: O((V + E) log V) with a binary heap
Correctness requirement: all edge weights must be non-negative. Dijkstra's fails with negative edge weights because once a vertex is extracted, its distance is considered final.
Produces: a shortest-path tree rooted at the source
Approach: dynamic programming over "intermediate vertices"
Let dist[i][j][k] = shortest path from i to j using only vertices {0, 1, ..., k} as intermediates
Recurrence: dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])
In practice, done in-place with a 2D matrix, iterating k as the outer loop
Time: O(V³), Space: O(V²)
Handles negative weights (but not negative cycles)
Detecting negative cycles: if dist[i][i] < 0 after running, there is a negative cycle through vertex i
BFS/DFS time complexity:
O(V + E) for both (every vertex and every edge is examined once)
Kruskal's:
O(E log E + E · α(V)) ≈ O(E log E)
Prim's with binary heap:
O((V + E) log V)
Dijkstra's with binary heap:
O((V + E) log V)
Floyd-Warshall:
Time: O(V³), Space: O(V²)
Relaxation (Dijkstra's core operation):
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
prev[v] = u
GPS navigation systems use variants of Dijkstra's algorithm to find the fastest route. Social network features like "people you may know" use BFS to find short connection paths. Network routing protocols use shortest-path algorithms. Power grid and telecommunications network design uses MST algorithms to minimise the total cost of wiring while keeping everything connected.
"Dijkstra's works with negative edge weights." It does not. Once a vertex is finalised (extracted from the priority queue), Dijkstra's assumes its distance is optimal. A negative edge could later provide a shorter path, breaking this assumption. Use Bellman-Ford for graphs with negative edges.
"BFS and DFS have different time complexities." They are both O(V + E). The difference is the order in which they visit nodes, not the total amount of work.
"A graph always has a unique MST." Only if all edge weights are distinct. If some weights are equal, there can be multiple valid MSTs with the same total weight.
"Prim's and Kruskal's produce different MSTs." If the MST is unique, they produce the same tree. If not, they may produce different valid MSTs depending on tie-breaking.
⚠️ Trace through BFS and DFS on a given graph, showing the order of vertex discovery and the resulting spanning tree.
⚠️ Run Kruskal's or Prim's on a weighted graph step by step. Know which data structures each algorithm uses internally.
⚠️ Trace Dijkstra's algorithm, showing the priority queue state and distance updates at each step.
⚠️ Know when Dijkstra's fails (negative weights) and what alternative to use (Bellman-Ford).
⚠️ Floyd-Warshall's recurrence and the meaning of the k variable (intermediate vertices) are testable.
⚠️ Understand the tradeoffs between adjacency matrix and adjacency list, especially in terms of time complexity for common operations.
True or false: BFS finds the shortest path in a weighted graph.
Fill in the blank: Kruskal's algorithm uses a ______ data structure to detect cycles.
True or false: Dijkstra's algorithm works correctly on graphs with negative edge weights.
Fill in the blank: Floyd-Warshall has a time complexity of ______.
True or false: An MST of a graph with V vertices always has exactly V - 1 edges.
Answers: 1. False (only in unweighted graphs). 2. Disjoint set (union-find). 3. False. 4. O(V³). 5. True.
Q: Given a graph with 6 vertices and 10 edges, would you prefer an adjacency matrix or adjacency list? Why?
A: With 6 vertices, the matrix is 6 × 6 = 36 entries, and the adjacency list stores 6 + 2(10) = 26 entries (each undirected edge appears twice). Both are small, so either works. For larger graphs, the ratio matters more: a sparse graph (E much less than V²) favours adjacency lists.
Q: Why does Prim's algorithm need a priority queue? Could you use an unsorted list instead?
A: You could, but finding the minimum-weight edge would take O(V) instead of O(log V) per extraction. With V extractions, Prim's with an unsorted list runs in O(V²), which is fine for dense graphs. With a binary heap, it runs in O((V + E) log V), which is better for sparse graphs.
Q: After running Floyd-Warshall, how do you reconstruct the actual shortest path from vertex i to vertex j?
A: Maintain a "next" matrix: next[i][j] stores the first vertex on the shortest path from i to j. When you find a shorter path through k, set next[i][j] = next[i][k]. To reconstruct: start at i, follow next[i][j] to the intermediate vertex, repeat until you reach j.
Q: Can Kruskal's algorithm be used on a directed graph?
A: MST is defined for undirected graphs. The directed equivalent is a minimum spanning arborescence (minimum cost to reach all vertices from a root in a directed graph), which requires a different algorithm, such as Edmonds' algorithm.
Graph traversals (BFS, DFS) build on stacks and queues from Week 3. Kruskal's algorithm relies on disjoint sets from Week 8. Prim's and Dijkstra's rely on heaps from Week 7. The shortest-path problems connect to dynamic programming concepts. Graphs are also the underlying structure for the probability and hashing topics later in the course (hash tables can be viewed as a mapping problem, and random graphs appear in probabilistic analysis).
graph, directed graph, undirected graph, weighted graph, digraph, vertex, edge, adjacency matrix, adjacency list, edge list, sparse graph, dense graph, BFS, breadth-first search, DFS, depth-first search, traversal, connected component, spanning tree, minimum spanning tree, MST, Kruskal, Prim, cut property, Dijkstra, shortest path, single-source shortest path, SSSP, relaxation, Floyd-Warshall, all-pairs shortest path, APSP, dynamic programming, negative weights, priority queue, CS 225, data structures, UIUC