Graph Algorithms
Peter M. Maurer
Baylor University
Graph Algorithms
Recursive DFS
Compute Start Time
Compute Finish Time
Strongly Connected Components: Compute Finish Times
Strongly Connected Components: Reverse the Edges
Strongly Connected Components: Sort into Decreasing Finish Order
Strongly Connected Components: DFS by Decreasing Finish
Strongly Connected Components
Biconnected Components
Bipartite Matching
Alternating Path
Reverse
Maximum Flow
An Augmenting Path
Compute Residual Network
DFS For Augmenting Path
Augment Part 1
Augment Part 2
Max Flow for Bipartite Match
Breadth First Search
Depth First Search
Connected Components
Connected Component DFS
Adjacency List Structure
Kruskal’s MST Algorithm
Prim/Dijkstra MST Initialization
Prim/Dijkstra Body
Dijkstra’s Shortest Path
Dijkstra’s S.P. Body
Dijkstra’s “Other” Algorithm
The RELAX Algorithm
The Bellman-Ford Algorithm