COMP90038 · Algorithms And Complexity
Graphs and Traversal
Graphs are the data model behind a third of the subject, so the vocabulary and the two traversals have to be automatic. The chapter fixes the language — vertices and edges, directed vs undirected, weighted, paths, cycles, connectivity — and the two representations: the adjacency matrix (Θ(V²) space, O(1) edge lookup) and the adjacency list (Θ(V+E) space, fast iteration over neighbours), with the choice driven by whether the graph is dense or sparse. It then presents traversal as one framework with two policies: process the frontier as a stack → depth-first search or as a queue → breadth-first search, each running in O(V+E) on a list. From those traversals fall the exam-staple by-products: the DFS/BFS forest and its tree/back/cross edges, topological sort two ways (DFS post-order reversed, and Kahn's in-degree peeling), and connected components. Master one traversal skeleton and you get all of these for free.
What this chapter covers
- 01Graph vocabulary: directed / undirected, weighted, paths, cycles, connectivity
- 02Adjacency matrix (Θ(V²)) vs adjacency list (Θ(V+E)) — dense vs sparse
- 03The unified traversal framework: stack → DFS, queue → BFS, O(V+E)
- 04DFS / BFS forests and edge classification (tree / back / cross)
- 05Topological sort two ways; connected components
Worked example: topological sort by DFS post-order
- +2Run DFS, recording finish order. From a, visit b, then b→d, then d→e: e finishes, then d, then b. Back at a, visit c; c→d already done, so c finishes; finally a finishes.
- +1Finish (post-order) sequence: e, d, b, c, a.
- +1Reverse it. Topological order = a, c, b, d, e — every edge points from earlier to later.
Key terms
- Adjacency matrix
- A V×V boolean (or weight) matrix where entry [i][j] records the edge i→j. O(1) edge lookup but Θ(V²) space and Θ(V) to list a vertex's neighbours — best for dense graphs.
- Adjacency list
- Per vertex, a list of its neighbours. Θ(V+E) space and fast neighbour iteration, but O(degree) to test a specific edge — best for sparse graphs and the default for traversal, which runs in O(V+E) on it.
- Depth-first search (DFS)
- Traversal that explores as far as possible along each branch before backtracking, naturally implemented with a stack or recursion. Yields the DFS forest, classifies edges, and drives topological sort and cycle detection in O(V+E).
- Breadth-first search (BFS)
- Traversal that explores all neighbours at the current distance before moving outward, implemented with a queue. Finds shortest paths in unweighted graphs and layers vertices by distance from the source, in O(V+E).
- Topological sort
- A linear ordering of a directed acyclic graph's vertices such that every edge points forward. Computed by reversing DFS finish order, or by repeatedly removing in-degree-0 vertices (Kahn's algorithm); it exists iff the graph is acyclic.
Graphs and Traversal FAQ
When should I use a matrix versus a list?
Use an adjacency list for sparse graphs (E far below V²) and whenever you traverse, because traversal is O(V+E) on a list. Use a matrix for dense graphs or when you need O(1) edge-existence tests — for example Warshall's and Floyd's algorithms, which are inherently Θ(V²)/Θ(V³) and matrix-shaped anyway.
What is the difference between DFS and BFS, beyond the data structure?
DFS uses a stack and dives deep, exposing back edges (so it detects cycles) and giving topological order via finish times. BFS uses a queue and expands in distance layers, so it finds shortest paths in unweighted graphs. Both visit every vertex and edge once, O(V+E).
How do I do a topological sort by hand in the exam?
Either run DFS, list vertices in order of finishing, and reverse that list; or repeatedly remove a vertex with in-degree 0, appending it to the order and decrementing its neighbours' in-degrees. Both are O(V+E); the in-degree method is often quicker to do by hand on a small DAG.
Exam move
Drill one traversal skeleton until you can run it in the margin, because Q1 routinely asks for a DFS topological order or a BFS layering on a small graph, and Q3–Q10 designs lean on traversal as a sub-routine. Be able to state both representations' space and the O(V+E) traversal cost without hesitation, and practise classifying tree/back/cross edges and producing a topological order both ways. Recognising “reachability”, “shortest unweighted path” and “cycle detection” as DFS/BFS jobs is half the design battle.
