Speaker note: A tree let one node point at several children, but never back up and never sideways. Drop both of those restrictions — let any node point at any node — and a tree becomes a graph, the most general shape in this course.
Speaker note: Eight short animations carry the whole lecture; each appears once, exactly where its idea is introduced, and every one gets a second look at a harder or edge-case input.
Speaker note: Every term gets a full definition the first time it appears; this table just says where to find it again.
Speaker note: Open a terminal now if you want to run these live; every snippet on today's slides compiles and runs exactly as shown.
Speaker note: Nothing about the machinery is new this week — only a new shape for the data these two structures will hold.
Speaker note: Last week's "n nodes, n-1 edges, no cycle" rule was a special case; today that restriction is lifted entirely.
Speaker note: Every box on this map gets its own slides below, most with a short animation and a complete C/Java program.
Speaker note: Section 1 motivates the whole week with the single oldest problem in graph theory, then shows the same shape hiding in maps, friendships, and the web.
Speaker note: This is the actual question a small city asked itself in the 1700s — and it produced an entirely new branch of mathematics.
Speaker note: Euler never drew a single bridge in his paper — he threw away everything except which landmasses connect to which, which is precisely the idea of a graph.
Speaker note: Stripping away the map and keeping only "what connects to what" is the single most important move in this entire course.
Speaker note: This single counting argument, degree parity, is why the answer is "no" for any city shaped like Königsberg, not just that one.
Speaker note: "Vertices and edges" turned out to be one of the most reusable ideas in all of computer science.
Speaker note: Every "get directions" button you have ever tapped ran some form of a graph shortest-path algorithm underneath.
Speaker note: A friend suggestion feature is, underneath, almost always a short breadth-first search from your own vertex.
Speaker note: PageRank, the original Google ranking idea, is fundamentally a computation performed on this exact directed graph of links.
Speaker note: Keep this table in mind for the rest of the week — every traversal idea below is a tree idea with these three restrictions removed.
Speaker note: Every one of today's algorithms must work correctly even on the awkward cases this slide lists — that is exactly what the "edge case" animations below test.
Speaker note: Apply the parity rule from a few slides back.
Speaker note: Zero odd vertices gives a round trip back to the start; exactly two gives a one-way walk — anything else, no walk at all.
Speaker note: Section 2 builds the vocabulary every later section leans on — vertex, edge, degree, path, cycle — all on one worked example.
Speaker note: Almost everything this week — surprisingly, this two-set definition is the entire foundation.
Speaker note: This formal definition looks sparse on purpose — its power is exactly how few assumptions it makes.
Speaker note: Every one of these is pointed at, one at a time, in the animation right after this table.
Speaker note: An unweighted edge is really just a weighted edge whose weight always happens to be 1.
Speaker note: Degree splits into two only once direction exists — an undirected graph never needs "in" or "out" at all.
Speaker note: A graph that allows self-loops and multi-edges is sometimes specifically called a multigraph.
Speaker note: This distinction matters a great deal in Section 3, when choosing how to store a graph.
Speaker note: Every algorithm this week is built entirely out of these three small questions, asked over and over.
Speaker note: Normal example: 8 vertices, weighted, with a cycle, a self-loop, a multi-edge, and 2 components — every term from this section, on one graph.
Speaker note: 8 vertices, directed, with two separate cycles, a self-loop, a multi-edge and 2 weak components — in-degree and out-degree now genuinely differ per vertex.
Speaker note: One struct for an edge, one for the whole graph — every algorithm this week is built on exactly these two shapes.
Speaker note: In an undirected graph this single function already counts everything a vertex needs — no separate "in" version required.
Speaker note: Finding who points AT v means scanning every OTHER vertex's list — there is no shortcut without extra bookkeeping.
Speaker note: This asymmetry is a direct consequence of storing only outgoing edges, the adjacency-list choice Section 3 explains.
Speaker note: The hard-preset animation above was built specifically to make in-degree and out-degree disagree on most vertices.
Speaker note: Think about which direction a self-loop's single edge "points" in.
Speaker note: In an undirected graph, that same self-loop instead raises plain degree by 2, not 1 — direction changes the counting rule.
Speaker note: A graph is an idea; a program needs one concrete way to store it. This section builds the two standard choices, side by side, on the very same graphs.
Speaker note: There is no single best answer — the two structures below trade one operation's speed for the other's memory.
Speaker note: Both sections below build these from the exact same edge lists, so the two representations can be compared directly.
Speaker note: An undirected graph's matrix is always symmetric across its diagonal — that symmetry is what "either direction" means, written as numbers.
Speaker note: Normal example: 7 vertices, undirected, unweighted, 10 edges — watch the matrix fill in, one symmetric pair of cells at a time.
Speaker note: 5 vertices, every pair connected, 10 edges — the maximum possible for 5 vertices, and the matrix ends up completely full off the diagonal.
Speaker note: One assignment for a directed edge, two — mirrored — for an undirected one; that single "if" is the whole difference.
Speaker note: Zero the whole table first, then add one edge at a time — order does not matter, since each edge only touches its own two cells.
Speaker note: The matrix's cost never depends on how many edges actually exist — only on how many vertices could possibly exist.
Speaker note: This is the exact same linked-list node from Week 2, just reused: one field for the neighbor's id, one for "next".
Speaker note: Same normal example as the matrix: 7 vertices, undirected, unweighted, 10 edges — watch each edge append to one or two lists.
Speaker note: 8 vertices, directed, weighted, 10 edges including a reversed pair `P>R` and `R>P` — some vertices end up with an empty list, having no outgoing edge at all.
Speaker note: Exactly Week 2's singly linked list append: walk to the tail, then attach — nothing about graphs changes this pattern at all.
Speaker note: The self-loop check, `a != b`, exists so an undirected self-loop is not appended twice to the very same list.
Speaker note: has_edge is the one operation where the matrix strictly wins — the list must search, the matrix never does.
Speaker note: Three rows, and every later algorithm's complexity traces straight back to this one small table.
Speaker note: This is not a close call for the graphs this course actually cares about — the list wins by a wide margin.
Speaker note: Both structures store the exact same information — this choice is purely an engineering trade-off, never a correctness one.
Speaker note: A directed matrix's two "mirror" cells, matrix[a][b] and matrix[b][a], can legitimately hold two completely different values.
Speaker note: Square the vertex count, then compare that to the edge count.
Speaker note: This is exactly the situation Section 3's "sparse vs. dense" rule of thumb was written for.
Speaker note: BFS is level order, from Week 4, generalized from a tree to any graph — a queue, and nothing else, drives the whole algorithm.
Speaker note: "Nearest first" is the whole idea; the algorithm below is built to guarantee exactly that order.
Speaker note: Moore was solving a physical maze-wiring problem — the same queue-based idea turned out to generalize to any graph at all.
Speaker note: No ripple ever overtakes an earlier one — that ordering guarantee is exactly what makes BFS find shortest paths.
Speaker note: The BFS tree records, for every vertex, exactly one edge that first reached it — that is the parent pointer Section 8 reuses.
Speaker note: Normal example: 7 vertices, undirected, starting at A, 10 edges — watch the queue and the level[] row fill in together.
Speaker note: 9 vertices, 2 components — G, H, I are simply unreachable from A, the starting vertex, and stay grey for the whole run.
Speaker note: The exact circular queue from Week 3 — only the element type changed, from int scores to graph vertex ids.
Speaker note: Every unvisited neighbor gets marked, leveled, and given a parent pointer, all in the same instant it is first enqueued.
Speaker note: This O(V + E) bound is the single most common complexity result in graph algorithms, and it recurs all through this week.
Speaker note: BFS is secretly already solving the unweighted shortest-path problem; Section 8 just makes that fact explicit.
Speaker note: Any time the question is "fewest steps", not "shortest weighted distance", BFS is usually the right first tool to reach for.
Speaker note: Marking "visited" too late is the single most common BFS bug — the same vertex can be enqueued more than once.
Speaker note: Recall exactly what "level" was defined to mean, a few slides back.
Speaker note: This is the fact Section 8 turns into a full algorithm: level IS shortest-path length, for unweighted graphs.
Speaker note: DFS is preorder, from Week 4, generalized from a tree to any graph — recursion, and nothing else, drives the whole algorithm.
Speaker note: "Commit, then backtrack" is depth-first search in one sentence — the opposite strategy from BFS's ring-by-ring approach.
Speaker note: Recursion IS a stack, from Week 3 — every recursive dfs_visit call pushes a frame, and every return pops one.
Speaker note: A vertex is gray for exactly as long as it sits on the call stack — the moment it returns, it turns black.
Speaker note: Forward and cross edges cannot happen in an undirected graph — there, every non-tree edge you find is a back edge.
Speaker note: Normal example: 7 vertices, undirected, 4 back edges, 10 edges — watch the call stack column and disc/fin[] fill in together.
Speaker note: 6 vertices, directed, built specifically so a tree, a back, a forward, and a cross edge all appear in one single run.
Speaker note: One shared clock counts up on every discovery AND every finish — that is what makes disc/fin intervals nest correctly.
Speaker note: Three colors, three branches — the entire edge-classification idea from a few slides back, written as one if/else chain.
Speaker note: A disconnected graph's DFS produces not one tree but a DFS FOREST — one tree per component, exactly like Section 7's components.
Speaker note: BFS and DFS visit the very same set of vertices and edges — only the ORDER differs, never the total work.
Speaker note: This is not a hypothetical: a million-vertex chain graph really can crash a naive recursive DFS in practice.
Speaker note: On an undirected graph, the edge back to your immediate parent is not a real back edge — it is the same edge you just arrived on.
Speaker note: Recall exactly what "gray" means, and where a gray vertex currently sits.
Speaker note: This is exactly how graph-terminology.js detected the cycle it reported back in Section 2's animation.
Speaker note: Section 5's recursion risk motivates this section directly: the same algorithm, the same visit order, but with our own array-based stack instead of the call stack.
Speaker note: Yes — and the technique is one this course has already used once before, back in Week 4's iterative inorder traversal.
Speaker note: This is the exact same motivation as Week 4's iterative inorder traversal, now applied to a graph instead of a tree.
Speaker note: This single trick is the whole difference between "an explicit stack" and "an explicit stack that matches recursion exactly".
Speaker note: Same normal example as Section 5: 7 vertices, undirected, 4 back edges, 10 edges — the visit order comes out identical.
Speaker note: 10 vertices, 2 separate components — a fresh stack starts from each unvisited vertex, producing one tree per component, exactly as in Section 5.
Speaker note: The plainest possible array-based stack — one increment on push, one decrement on pop, nothing else.
Speaker note: The "if (visited[u]) continue" line matters: a vertex can be pushed more than once, and only the FIRST pop should count.
Speaker note: The whole point was never speed — it was avoiding a call-stack overflow that the recursive version risks on deep graphs.
Speaker note: Same order, same complexity, same output — this table is really about which stack does the remembering.
Speaker note: Skipping the stale-entry check is the single most common bug when converting recursion to an explicit stack by hand.
Speaker note: Recall what the stale-entry check on the previous code slide is specifically there to prevent.
Speaker note: That discard is exactly the "stale entry" case the code's `if (visited[u]) continue` line handles.
Speaker note: Section 7 reuses BFS itself, unchanged, as a subroutine — the only new idea is calling it once per unvisited vertex and giving each run its own label.
Speaker note: Section 1 already warned that a graph need not be connected; this section answers "how disconnected, exactly?".
Speaker note: "Weak" connectivity means we treat every directed edge as if it were undirected, just for this one question.
Speaker note: Normal example: 10 vertices, undirected, 2 components (two separate 5-cycles), 10 edges — watch each BFS claim its own circle.
Speaker note: 12 vertices, undirected, 4 separate triangle components, 12 edges — the most components this section's animation ever shows at once.
Speaker note: This is Section 4's plain BFS, completely unchanged, except that "visited" is now "comp_of == -1" and the mark left behind is an id, not just true/false.
Speaker note: next_id both counts the components AND becomes each new component's label — one variable, two jobs.
Speaker note: Running BFS several times, once per component, still adds up to the same O(V + E) as one single BFS over the whole graph.
Speaker note: Flood fill is worth naming specifically — it is exactly this algorithm, run on a grid of pixels instead of a graph of vertices.
Speaker note: Strong connectivity (respecting direction) is a genuinely harder problem, needing more than plain BFS — outside this week's scope.
Speaker note: Recall exactly what "direction is ignored" was said to mean, a few slides back.
Speaker note: Strong connectivity would require BOTH A>B and a path back from B to A — a stricter, different question entirely.
Speaker note: Section 4 already computed every vertex's level; this section makes that fact fully explicit by reconstructing the actual shortest path, not just its length.
Speaker note: Yes — and the mechanism is one already sitting inside BFS's output: the parent pointer, recorded the instant each vertex is first reached.
Speaker note: Nothing here is new machinery — it is Section 4's BFS, plus one short walk backward through the parent pointers it already built.
Speaker note: Normal example: 7 vertices, undirected, s=A, t=F, 10 edges — watch parent[] fill in during BFS, then get walked backward at the end.
Speaker note: 9 vertices, s=A, t=H, in 2 separate components — the queue empties with t never visited, so no path can be reported at all.
Speaker note: Identical to Section 4's BFS loop, with one difference: this version's ONLY goal is filling in parent_of correctly.
Speaker note: The walk builds the path backward, from t to s, purely because that is the only direction the parent pointers go — reversing at the end fixes the order.
Speaker note: Reconstructing the actual path is essentially free on top of a BFS you would often be running anyway.
Speaker note: Only the LENGTH is guaranteed unique — the exact sequence of vertices depends on tie-breaking choices like alphabetical order.
Speaker note: BFS's plain queue always expands the nearest UNVISITED vertex by edge count; Dijkstra swaps in a priority queue so it expands by actual distance instead.
Speaker note: Every one of these three mistakes still runs without crashing — the bug only shows up in the printed path itself.
Speaker note: Recall the very first check the walk-back code makes, on the slide a few back.
Speaker note: This is precisely the situation the "no-path" edge-case animation above was built to demonstrate.
Speaker note: Two representations, one table of trade-offs — every later algorithm's complexity traces back to this row.
Speaker note: Every one of these four rows is built from the same two moves: enqueue/dequeue, or push/pop.
Speaker note: If a student remembers only one sentence from today, this is the one worth remembering.
Speaker note: These mirror the self-check quiz at the end of the written notes, one question per slide, with a shorter set here.
Speaker note: Ask, wait, then advance.
Speaker note: For n vertices, a complete undirected graph always has n(n-1)/2 edges.