COMP9123 — Data Structures & Algorithms
Week 8: Graphs
Week 8 leaves tree-shaped structure behind and moves into general networks. The lecture first teaches the language of graphs, then shows how the same graph can behave very differently depending on its representation, and finally builds the two traversal workhorses you will use for the rest of the course: DFS and BFS.
A strong Week 8 answer explains not just how to traverse a graph, but why that traversal is correct and why the chosen representation makes the asymptotic bound possible.
Graph Language: The Vocabulary You Need Before Any Algorithm Makes Sense
Graphs are the right abstraction when objects are connected in ways that are too flexible for arrays, lists, or trees alone. Week 8 begins by making that language precise, because traversal arguments depend on these definitions being automatic in your head.
| Concept | Meaning | Why it matters later |
|---|---|---|
| Vertex / edge | Vertices are objects; edges record relationships between them. | All later algorithms talk about discovering vertices by examining edges. |
| Directed vs undirected | A directed edge is ordered; an undirected edge is symmetric. | Degree, reachability, and traversal behavior depend on this distinction. |
| Path / cycle | A path links consecutive vertices by edges; a cycle starts and ends at the same vertex. | Cycle detection and bridge reasoning are impossible if this language is fuzzy. |
| Connected component | A maximal set of vertices that can reach each other. | DFS and BFS naturally expose components and spanning forests. |
Trees inside graph language
An unrooted tree is just a connected acyclic graph. A forest is an acyclic graph whose components are trees.
Spanning tree
A spanning tree keeps every vertex but throws away enough edges to leave one connected acyclic skeleton.
Foundational fact
Every tree on \(n\) vertices has exactly \(n-1\) edges. That fact keeps reappearing in proofs and sanity checks.
Professor lens: the lecture is quietly reframing old tree knowledge as a special case of graph structure. That matters because later graph algorithms often detect tree-like substructures rather than working on trees given in advance.
Graph ADT: The Abstraction Is Separate from the Representation
Before choosing adjacency lists or matrices, the lecture inserts a useful abstraction layer: the Graph ADT. That move is the graph analogue of what Weeks 5 to 7 did for trees, maps, and hash tables. We want to talk about graph operations without committing too early to how the graph is stored.
| ADT object | Stores | Typical operations |
|---|---|---|
| Vertex | An associated element, such as an airport code | getElement() |
| Edge | An associated element, such as route distance or flight number | getElement(), endpoint queries |
| Graph | The overall incidence structure | vertices(), edges(), degree(v), incidentEdges(v), getEdge(u,v), insertion, removal |
Directed and undirected variants
The same ADT story branches into different degree and incident-edge operations once orientation matters. That is why the lecture shows directed and undirected alternatives separately.
Why this abstraction matters
Once the ADT is fixed, the representation table becomes meaningful: you can compare adjacency lists and matrices fairly because they support the same interface.
Representations: Adjacency List, Adjacency Matrix, and the Cost of the Same Query
Week 8 makes one of the course's most important design points: the graph itself is the same, but the representation changes what is cheap. You do not pick a representation because it is “standard.” You pick it because your workload cares more about neighbor iteration, edge lookup, insertion, or memory usage.
| Representation | Space | What it does well | Where it hurts |
|---|---|---|---|
| Adjacency list | \(O(n+m)\) | Iterating over neighbors, sparse graphs, traversals in \(O(n+m)\) | getEdge(u,v) is not constant-time in general |
| Adjacency matrix | \(O(n^2)\) | Constant-time edge-existence queries and dense graphs | Scanning neighbors costs \(O(n)\) even if very few edges exist |
| Edge list | \(O(m)\) | Very compact and easy to store or sort | Neighbor iteration requires filtering through unrelated edges |
Most graph traversals in this course assume adjacency lists, because the whole \(O(n+m)\) story depends on spending time only on vertices and on edges that actually exist.
DFS: Go Deep, Backtrack, and Build a Spanning Forest as You Go
Depth-first search is the first traversal framework the lecture develops. Operationally it is simple: keep following unexplored edges whenever possible, and backtrack when stuck. Conceptually it is powerful because the parent pointers and recursion stack expose structural information about the graph.
Initialize all vertices
Set visited[u] to false and parent[u] to None so the traversal can restart on new components if needed.
Visit deeply
Whenever DFS reaches an unvisited neighbor, that edge becomes a DFS tree edge and the search continues recursively.
Backtrack with structure
Non-tree edges tell you that there is some alternative connection, which is exactly why DFS becomes the basis for cycle, bridge, and articulation reasoning.
| DFS fact | Why it matters |
|---|---|
DFS_visit(v) visits the entire connected component of v |
This is why DFS solves connected components and connectivity testing. |
| Parent edges in one component form a spanning tree | The traversal is not just exploring; it is building a useful subgraph. |
| Running the outer loop over all vertices yields a spanning forest | Disconnected graphs require restarting the search, which the tutorial explicitly tests. |
The setup loop touches each vertex a constant number of times, which contributes \(O(n)\).
Across all recursive calls, each adjacency-list entry is examined at most once, contributing \(O(m)\).
Adding vertex work and edge work gives total time \(O(n+m)\).
The lecture's applications list is worth memorizing as a family: path finding, cycle finding, connectivity, connected components, spanning trees, and then more advanced algorithms like cut edges and cut vertices built on top.
Cut Edges: DFS Is Valuable Because It Can Detect Fragile Connections
A cut edge, or bridge, is an edge whose removal disconnects part of the graph. The lecture first contrasts the naive approach with the real one. Re-running DFS after deleting every edge is far too slow. The whole point is to extract bridge information during one DFS.
| Approach | Idea | Cost |
|---|---|---|
| Naive | Delete each edge and test connectivity again | Too expensive: \(O(m^2)\) or worse in the lecture's discussion |
| DFS-based | Compute one DFS tree plus level and down_and_up values |
Linear time: \(O(n+m)\) |
For a DFS tree edge \((u,v)\) with \(u=\text{parent}[v]\), the lecture states that \((u,v)\) is not a cut edge if and only if down_and_up[v] ≤ level[u]. Intuitively, the subtree of v can still climb back to u or above using one back edge.
The bridge idea is really about redundancy. If the subtree under v has no route back except through \((u,v)\), then that edge is a single point of failure.
BFS: Expand by Layers and Turn Distance into Structure
Breadth-first search explores outward from a start vertex one layer at a time. That single operational difference from DFS changes everything: BFS is the traversal that respects shortest-path distance in unweighted graphs.
Start with \(L_0=\{s\}\)
The start vertex is the whole first layer, at distance 0 from itself.
Process the current frontier
All unseen neighbors of the current layer become the next layer, so distance grows in exact one-edge steps.
Use parent pointers to recover paths
The first time a vertex is discovered is through a shortest unweighted path from the source.
Core BFS facts
If \(v\) lies in layer \(L_i\), then the BFS tree contains a path from the start vertex to \(v\) using exactly \(i\) edges, and no path in the graph can use fewer than \(i\) edges.
Tutorial payoff
The bipartite test comes directly from layer reasoning: if an edge stays within one BFS layer, the graph cannot be bipartite under that layering.
BFS also needs a restart loop for disconnected graphs if the goal is to cover every vertex. The tutorial deliberately checks whether you notice that “run from one source” and “fully traverse the graph” are different tasks.
Tutorial & problem lens: Week 8 is really about graph thinking, not memorizing one traversal
The tutorial makes Week 8 much richer than a list of definitions. It asks you to use graph models and traversal invariants to solve concrete problems, and that is the mindset you want before moving into shortest paths and greedy graph algorithms later.
Warm-up habits the sheet wants
- Run BFS as layers, not as a vague queue process.
- Run DFS as a specific visitation order, not just “go deep somehow.”
- Restart the search on disconnected graphs so every component is covered.
- Use BFS layer numbers to prove local facts like \(|d(u)-d(v)| \le 1\) for every edge.
Problem-solving patterns
- Bipartite testing via BFS layers and parity.
- Cycle finding in linear time from adjacency lists.
small(i)by scanning connected components and propagating a component minimum.- A get-stuck vertex in \(O(n)\) from an adjacency matrix by avoiding a full matrix scan.
- Cut edges and cut vertices from the lecture's DFS machinery.
- Snakes and Ladders modeled as a shortest-path problem on a graph.
How to study this week well
Draw small graphs and trace them. Week 8 punishes passive reading because graph algorithms are about state evolution: visited flags, parent links, layers, and back edges. If you can sketch one traversal by hand and narrate why each vertex enters when it does, you actually understand the page.
There is no bundled code file this week, but the lecture explicitly points you to an Ed lesson for adjacency-list implementation. That is a hint that representation details still matter even when the tutorial sheet is mostly algorithmic.
Quiz Hub & spaced review
Use the inline checks to make sure you really own three high-value ideas first: representation choice, bridge intuition, and BFS shortest-path layering. Then use the mixed tools to rehearse those ideas out of context.
Recommended sequence. Do one clean hand-trace of DFS and BFS on a small graph, answer the inline checks without notes, then move to flashcards or the Quiz Hub to see whether the graph vocabulary and traversal guarantees are now automatic.