Chapter 4: Graph Theory & Network Algorithms

Graphs and the algorithms that traverse and exploit them: representations, traversals, topological sort, spanning trees, shortest paths, and flow.

• Graph Representations (Adjacency Matrix, Adjacency List, Edge List, Sparsity Representations, Graph Neural Network Data Structures)
• Graph Traversals: Breadth-First Search (BFS) and Depth-First Search (DFS)
• Topological Sorting & Strongly Connected Components (Tarjan’s, Kosaraju’s)
• Minimum Spanning Trees (Kruskal’s, Prim’s Algorithms)
• Shortest Path Algorithms & Heuristic Search: Single-Source (Dijkstra’s, Bellman-Ford, A*, IDA*), Bidirectional Search, & All-Pairs (Floyd-Warshall Space Optimizations, Johnson’s Algorithm, Matrix Multiplication Paths)
• Network Flow & Matching (Ford-Fulkerson, Edmonds-Karp, Dinic’s, Hopcroft-Karp)
• Chapter 4 References