Graphs

A graph is things and the links between them: roads between towns, follows between people, tasks that wait on other tasks. These are the standard ways to explore one, order it, find shortest routes and connect it cheaply. Each one has a live visualizer running the real code.

1. 01Breadth-first searchExplore in rings of distance with a queue, finding the fewest hops to everything.O(V + E)
2. 02Depth-first searchFollow one path as deep as it goes, then back up and try the next.O(V + E)
3. 03Cycle detectionSpot a loop in a directed graph by finding an edge back into the current path.O(V + E)
4. 04Topological sortOrder tasks so every task comes after the ones it depends on.O(V + E)
5. 05Dijkstra's algorithmShortest routes by always settling the closest unfinished node next.O(E log V)
6. 06Bellman-FordShortest routes that allow negative weights, by relaxing every edge n − 1 times.O(V · E)
7. 07Union-findTrack which nodes are connected as links are added, almost in constant time.O(α(n))
8. 08Kruskal's algorithmBuild the cheapest network by adding the lightest edge that joins two groups.O(E log E)
9. 09Prim's algorithmGrow the cheapest network outward from one node, one lightest edge at a time.O(E log V)
10. 10Bipartite checkColour nodes in two colours so no edge joins two of the same.O(V + E)