Advanced · Module 13
Graphs
Networks of nodes and edges: how to store them and walk them breadth-first and depth-first.
A graph is any set of things joined by connections: roads, friendships, links, dependencies, moves in a puzzle. This module covers how to store graphs, the two fundamental ways to explore them, breadth-first and depth-first, and what those explorations reveal: shortest paths when every step counts the same, connected regions, cycles, and the orders in which dependent tasks can run.
- 1Representing graphsPro — members onlyA graph is a set of vertices joined by edges. How you store it, as adjacency lists, an adjacency matrix or an edge list, decides the cost of every algorithm you run on it.13 min
- 2Breadth-first searchPro — members onlyBreadth-first search explores a graph in rings of increasing distance from the start, using a queue and a visited set. In an unweighted graph, the first time it reaches a vertex is along a shortest path.14 min
- 3Depth-first searchPro — members onlyDepth-first search follows one path as far as it can, then backs up and tries the next. It is the natural way to flood a region, explore every possibility, or ask what is reachable, as long as you watch its depth.14 min
- 4Cycles and connected componentsPro — members onlyOne walk over a graph can split it into connected pieces, tell whether it is a tree, and find cycles. Directed graphs need one extra idea: remembering which vertices are on the current path.14 min
- 5Topological sortPro — members onlyA topological order lists the vertices of a directed acyclic graph so that every edge points forward: everything comes after what it depends on. Kahn's algorithm builds one with in-degrees and a queue, and detects cycles for free.14 min