Graphs
Nodes, edges, and the searches that ripple across them.
Graphs progress0 / 16
- Graph BasicsThings, plus the connections between them.5m
- List vs MatrixStore the edges you have, or a cell for every pair you don't.5m
- Breadth-First SearchSweep outward one ring at a time, using a queue.6m
- Depth-First SearchCommit to one branch until it dead-ends, then back up.5m
- Connected ComponentsCount the islands by starting a fresh sweep on each one.5m
- Shortest Path, UnweightedBFS already found it — store parents to read it back.6m
- Dijkstra's AlgorithmWhen edges cost different amounts, always settle the nearest first.6m
- Topological SortOrder the steps so nothing runs before what it depends on.6m
- Bellman-FordRelax every edge, V-1 times, and negative weights stop being a problem.6m
- Kruskal's Spanning TreeBuy the cheapest cable that joins two pieces you have not joined yet.6m
- Prim's Spanning TreeOne tree that grows, always by its cheapest way out.6m
- Bipartite CheckTwo colours, no neighbour sharing one — or the split is impossible.5m
- Cycles in a Directed GraphGrey means still on the path — meet grey again and you have looped.6m
- Graphs You Never BuildGenerate the neighbours on demand and BFS works the same.6m
- Multi-Source BFSSeed the queue with every source and one sweep answers them all.5m
- Strongly Connected PartsGroups where every node can reach every other — found in two passes.7m
Quiz yourself: 3 questions from this module
1 / 3