Graphs¶
Networks of things and the classic algorithms on them: representations, breadth-first and depth-first search, topological order, connectivity, union-find, minimum spanning trees, shortest paths and maximum flow. Every algorithm is traced on small graphs and then checked against NetworkX.
This part builds on Linear structures and Trees.
2 of 9 topics ready, listed in reading order
Graphs and their representationsTerminology, adjacency matrices and lists, edge lists, the handshake lemma and the special graphs that recur.Planned
Breadth-first and depth-first searchBFS layers and fewest-hop paths, DFS discovery and finish times, edge classification and iterative DFS.ReadyTopological sortingKahn's algorithm and the DFS order, cycle detection and scheduling on directed acyclic graphs.Planned
Connected componentsComponents of undirected graphs, strongly connected components with Kosaraju and Tarjan, bridges and articulation points.Planned
Union-findDisjoint sets with union by rank and path compression, and why the cost is nearly constant.Planned
Minimum spanning treesThe cut property, Kruskal's and Prim's algorithms traced edge by edge, and Boruvka's algorithm.Planned
Single-source shortest pathsRelaxation, Dijkstra's algorithm with a heap, Bellman-Ford and negative cycles, shortest paths in a DAG, and A* as an extension.ReadyAll-pairs shortest pathsFloyd-Warshall, Warshall's transitive closure, shortest paths as matrix multiplication with repeated squaring, and Johnson's reweighting.Planned
Network flowMaximum flow with Ford-Fulkerson and Edmonds-Karp, the max-flow min-cut theorem and bipartite matching.Planned