Difficulty: Intermediate to Advanced | Prerequisites: Trees, queues, stacks, basic set/map operations, heaps (for Dijkstra's and Prim's).
Graphs are the most general-purpose data structure in this course. Trees, linked lists, and even arrays can be viewed as special cases of graphs. Once you understand how to represent and traverse a graph, a large number of real-world problems (routing, scheduling, social networks, dependency resolution) become tractable. Iterators are a lighter topic, but they tie into how you actually walk through these structures in code.
A graph is a collection of vertices connected by edges, and the way you store it (adjacency list, adjacency matrix, or edge list) determines the time and space cost of every operation you run on it. The core algorithms, BFS, DFS, Dijkstra's, Kruskal's, Prim's, and topological sort, each solve a different class of problem but all depend on choosing the right representation. Iterators are the C++ mechanism for walking through any container (including graphs and trees) without exposing its internal layout.
Graph
A data structure consisting of a set of vertices (nodes) and a set of edges (connections between vertices). In simple terms, dots and lines between them.
Vertex (node)
A single element in a graph. Vertices hold data or serve as identifiers; edges define relationships between them.
Edge
A connection between two vertices. Can be directed (one-way) or undirected (two-way), and can carry a weight (a numeric cost).
Directed graph (digraph)
A graph where every edge has a direction: edge (u, v) goes from u to v but not necessarily from v to u. Think of one-way streets.
Undirected graph
A graph where edges have no direction: edge (u, v) connects u to v in both directions. Think of a two-way road.
Weighted graph
A graph where each edge carries a numeric weight representing cost, distance, capacity, or some other quantity.
Adjacency list
A graph representation using an array of lists. Each vertex stores a list of its neighbours. Space-efficient for sparse graphs. In C++, typically vector.
Adjacency matrix
A graph representation using a 2D array where matrix[i][j] = 1 (or the edge weight) if an edge exists from vertex i to vertex j, and 0 otherwise. Fast edge lookup but uses O(V^2) space.
Edge list
A graph representation as a flat list of (u, v) pairs (with optional weights). Compact and convenient for algorithms like Kruskal's that process edges in sorted order.
Degree
The number of edges connected to a vertex. In a directed graph, this splits into in-degree (edges coming in) and out-degree (edges going out).
Path
A sequence of vertices where each consecutive pair is connected by an edge.
Cycle
A path that starts and ends at the same vertex with no repeated edges.
Connected graph
An undirected graph where every pair of vertices has a path between them.
DAG (directed acyclic graph)
A directed graph with no cycles. DAGs model dependency structures and are the input for topological sort.
BFS (breadth-first search)
A graph traversal that explores all neighbours of a vertex before moving to the next level. Uses a queue. Finds shortest paths in unweighted graphs.
DFS (depth-first search)
A graph traversal that follows one path as deep as possible before backtracking. Uses a stack (or recursion). Useful for cycle detection, topological sorting, and connected component labelling.
Dijkstra's algorithm
A greedy algorithm that finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights. Uses a min-priority queue (heap).
Kruskal's algorithm
A greedy MST algorithm that sorts all edges by weight and adds them one by one, skipping any edge that would create a cycle (checked via union-find).
Prim's algorithm
A greedy MST algorithm that grows a single tree from a starting vertex, always adding the cheapest edge that connects a new vertex to the tree. Uses a min-priority queue.
Topological sort
A linear ordering of the vertices of a DAG such that for every directed edge (u, v), u appears before v. Used for scheduling, build systems, and prerequisite resolution.
Iterator
An object that provides sequential access to the elements of a container without exposing the container's internal representation. Think of it as a bookmark that knows how to move forward through a collection.
begin() / end()
Standard C++ functions that return iterators pointing to the first element and one-past-the-last element of a container, respectively. Together they define the range a loop can traverse.
Const iterator
An iterator that provides read-only access to elements. Prevents modification of the container's contents during traversal.
A graph G = (V, E) is defined by a set of vertices V and a set of edges E
Key classification axes:
Directed vs undirected: Does the edge (u, v) imply (v, u)?
Weighted vs unweighted: Do edges carry numeric costs?
Cyclic vs acyclic: Can you follow edges and return to the same vertex?
Important vocabulary: adjacent (two vertices share an edge), degree (number of edges at a vertex), path (sequence of edges), cycle (a path that returns to its start), connected (every vertex can reach every other)
Adjacency list: An array where each entry holds a list of that vertex's neighbours. Space: O(V + E). Checking whether a specific edge exists costs O(degree of the vertex). Best for sparse graphs
Adjacency matrix: A V x V grid. Space: O(V^2). Checking whether a specific edge exists costs O(1). Best for dense graphs or when you need constant-time edge queries
Edge list: A simple list of all edges. Space: O(E). No fast neighbour lookup, but convenient for algorithms that iterate over all edges (Kruskal's). Good when the graph is given as a list of connections
BFS (breadth-first search):
Uses a queue. Visit the source, enqueue it, then repeatedly dequeue a vertex, visit all its unvisited neighbours, and enqueue them
Explores vertices level by level (all vertices at distance 1, then distance 2, etc.)
Finds shortest paths in unweighted graphs
Time: O(V + E) with an adjacency list
DFS (depth-first search):
Uses a stack (explicit or via recursion). Visit the source, push it, then go as deep as possible before backtracking
Useful for cycle detection, topological sorting, finding connected components, and solving mazes
Time: O(V + E) with an adjacency list
Dijkstra's algorithm:
Solves single-source shortest paths in weighted graphs with non-negative edge weights
Uses a min-priority queue (heap). Start at the source with distance 0; repeatedly extract the vertex with the smallest tentative distance, relax its neighbours
Time: O((V + E) log V) with a binary heap
Does not work with negative edge weights
Kruskal's algorithm (MST):
Sort all edges by weight. Process them in order: add each edge unless it creates a cycle (use union-find to check)
Time: O(E log E) for sorting, plus near-linear union-find operations
Works well with an edge list representation
Prim's algorithm (MST):
Grow the MST from a starting vertex. Use a min-priority queue to always add the cheapest edge connecting the growing tree to a new vertex
Time: O((V + E) log V) with a binary heap
Works well with an adjacency list representation
Topological sort:
Applies only to DAGs (directed acyclic graphs)
Produces a linear ordering where every directed edge (u, v) has u before v
Two common approaches: DFS-based (post-order reversal) and Kahn's algorithm (BFS with in-degree tracking)
Used for scheduling, build systems, and prerequisite resolution
Iterators abstract away the traversal of a container. You do not need to know whether the underlying structure is an array, a linked list, or a tree
Core interface in C++:
begin() returns an iterator to the first element
end() returns an iterator to one past the last element
++ advances the iterator
* dereferences (accesses the current element)
Const iterators (cbegin(), cend()) prevent modification during traversal
Range-based for loops (for (auto& x : container)) use iterators behind the scenes
STL algorithms like std::find, std::sort, and std::for_each all operate on iterator ranges
You can write custom iterators for your own data structures (trees, graphs) to make them compatible with the STL
Representation | Space | Edge lookup | Iterate neighbours | Best for |
|---|---|---|---|---|
Adjacency list | O(V + E) | O(deg(v)) | O(deg(v)) | Sparse graphs |
Adjacency matrix | O(V^2) | O(1) | O(V) | Dense graphs, fast edge queries |
Edge list | O(E) | O(E) | O(E) | Kruskal's, edge-sorted algorithms |
Algorithm | Time (with adjacency list + binary heap where applicable) | Purpose |
|---|---|---|
BFS | O(V + E) | Traversal, shortest path (unweighted) |
DFS | O(V + E) | Traversal, cycle detection, topological sort |
Dijkstra's | O((V + E) log V) | Shortest path (weighted, non-negative) |
Kruskal's | O(E log E) | Minimum spanning tree |
Prim's | O((V + E) log V) | Minimum spanning tree |
Topological sort | O(V + E) | Linear ordering of a DAG |
Google Maps uses Dijkstra's algorithm (and its variants) to find the fastest route between two locations. Package managers like npm and pip use topological sort to resolve dependency order. Social networks are graphs where people are vertices and friendships are edges, and BFS can find degrees of separation between users.
Students often think Dijkstra's works with negative edge weights. It does not. Negative weights require Bellman-Ford
Students confuse BFS and DFS outputs. BFS gives shortest paths in unweighted graphs; DFS does not. If a question asks for the shortest path, reach for BFS (unweighted) or Dijkstra's (weighted)
Students sometimes think an adjacency matrix is always better because edge lookup is O(1). For sparse graphs, the O(V^2) space cost is wasteful, and iterating over all neighbours costs O(V) instead of O(deg(v))
Students mix up Kruskal's and Prim's. Kruskal's sorts edges globally and uses union-find; Prim's grows a tree from a vertex and uses a priority queue. Both produce the same MST (assuming unique weights), but they approach the problem differently
Expect a question asking you to trace BFS or DFS on a given graph, listing vertices in the order visited
Know when to use each representation: if the question gives you a sparse graph, say adjacency list and explain why
Dijkstra's runtime and its requirement for non-negative weights are frequently tested
Kruskal's vs Prim's: be prepared to state which data structures each algorithm relies on and to trace each on a small weighted graph
Topological sort on a DAG: be ready to produce the ordering using either DFS post-order or Kahn's BFS approach
Iterator questions tend to be lighter: know the interface (begin, end, ++, *) and the difference between const and non-const iterators
True or false: Dijkstra's algorithm works correctly on graphs with negative edge weights.
Fill in the blank: BFS uses a ____, while DFS uses a ____.
True or false: An adjacency matrix uses O(V + E) space.
Fill in the blank: Kruskal's algorithm detects cycles using ____.
True or false: end() returns an iterator pointing to the last element of a container.
Answers: 1. False (it requires non-negative weights). 2. Queue; stack (or recursion). 3. False (O(V^2)). 4. Union-find (disjoint sets). 5. False (it points to one past the last element).
Q: Given a graph with vertices {A, B, C, D, E} and edges A-B, A-C, B-D, C-D, D-E, trace BFS starting from A.
A: Visit A, enqueue A. Dequeue A, visit neighbours B and C (enqueue both). Dequeue B, visit neighbour D (enqueue). Dequeue C, D already visited. Dequeue D, visit neighbour E (enqueue). Dequeue E, no unvisited neighbours. BFS order: A, B, C, D, E.
Q: When would you choose an adjacency matrix over an adjacency list?
A: When the graph is dense (the number of edges is close to V^2) or when you need O(1) edge existence checks. For sparse graphs, an adjacency list is more space-efficient and faster for neighbour iteration.
Q: Explain why topological sort is only defined for DAGs.
A: A topological ordering requires that for every edge (u, v), u appears before v. If the graph has a cycle, there is no way to satisfy this: following the cycle, each vertex would need to appear both before and after some other vertex in the cycle.
Q: Describe how Kruskal's algorithm builds a minimum spanning tree.
A: Sort all edges by weight. Initialise a disjoint set with each vertex as its own component. Process edges in order: for each edge (u, v), call find(u) and find(v). If they are in different components, add the edge to the MST and call union(u, v). If they are in the same component, skip the edge (it would create a cycle). Stop when the MST has V - 1 edges.
Q: What is the difference between a const iterator and a non-const iterator?
A: A non-const iterator allows both reading and modifying the element it points to. A const iterator allows only reading. Use const iterators when you want to traverse a container without any risk of accidentally changing its contents.
Graphs connect directly to heaps: Dijkstra's and Prim's algorithms both rely on a min-priority queue, typically implemented as a binary heap. They also connect to disjoint sets: Kruskal's algorithm uses union-find for cycle detection. Iterators connect to every container in the STL, and writing a custom iterator for a graph or tree is a common assignment that ties data structure internals to the C++ interface conventions.
graph, vertex, edge, node, directed graph, undirected graph, weighted graph, adjacency list, adjacency matrix, edge list, BFS, breadth-first search, DFS, depth-first search, Dijkstra's algorithm, shortest path, Kruskal's algorithm, Prim's algorithm, minimum spanning tree, MST, topological sort, DAG, directed acyclic graph, cycle detection, connected components, iterator, begin, end, const iterator, range-based for loop, STL algorithms, DSA exam 4, data structures UIUC