170: DSA - Graphs and Traversals
Learning outcomes
- represent directed and undirected graphs;
- use BFS and DFS with explicit visited state;
- detect cycles and produce a topological order.
Practice
Implement a dependency planner. Return a valid order or a cycle error. Compare adjacency lists with matrices and test disconnected nodes, self-loops, duplicate edges, and an empty graph.
Lesson and worked example
Represent sparse input as Map<Node, Set<Node>> so duplicate edges do not inflate indegrees. Kahn's algorithm starts with every zero-indegree node, removes it, decrements dependents, and appends newly free nodes. For compile -> test and compile -> package, either compile,test,package or compile,package,test is valid. If fewer than V nodes are emitted, a cycle exists. DFS gives the same result with three colors: visiting a gray node is a back edge.
BFS gives shortest paths only when every edge has equal cost. Mark on enqueue, not dequeue, so a node is queued once. For an undirected graph, cycle detection must ignore the immediate parent; for a directed graph, use recursion-stack/gray state.
Tests and rubric
Test empty and disconnected graphs, isolated nodes, duplicate edges, self-loops, a two-node cycle, a valid diamond dependency, unknown endpoints, and a graph with multiple valid orders. Score 2 points each for representation choice, traversal invariant, cycle result, complexity O(V + E), and deterministic/clear output contract. State whether output order must be lexicographically stable.
Checkpoint
Explain when BFS gives shortest unweighted paths, why marking visited on enqueue matters, and how topological sorting reveals a cycle.
Representation tradeoff
An adjacency list uses O(V + E) space and is the usual choice for sparse application graphs. A matrix uses O(V^2) space but gives constant-time edge lookup. Keep graph identity separate from display labels; duplicate labels are valid unless the problem forbids them. Mark a node when queued, not when removed, to avoid duplicate work.