Books Questions (Problems) Table of Contents: Route Between Nodes Custom Questions Table of Contents: Graph traversal DFS (Depth-First Search) BFS (Breadth-First Search) Connected components, bridges, articulations points Finding Connected Components Finding Bridges in O(N+M) Finding Bridges Online Finding Articulation Points in O(N+M) Strongly Connected Components and Condensation Graph Strong Orientation Single-source shortest paths Dijkstra - finding shortest paths from given vertex Dijkstra on sparse graphs Bellman-Ford - finding shortest paths with negative weights 0-1 BFS D´Esopo-Pape algorithm All-pairs shortest paths Floyd-Warshall - finding all shortest paths Number of paths of fixed length / Shortest paths of fixed length Spanning trees Minimum Spanning Tree - Prim's Algorithm Minimum Spanning Tree - Kruskal Minimum Spanning Tree - Kruskal with Disjoint Set Union Second best Minimum Spanning Tree - Using Kruskal and Lowest Common Ancestor Kirchhoff Theorem Prüfer code Cycles Checking a graph for acyclicity and finding a cycle in O(M) Finding a Negative Cycle in the Graph Eulerian Path Lowest common ancestor Lowest Common Ancestor Lowest Common Ancestor - Binary Lifting Lowest Common Ancestor - Farach-Colton and Bender algorithm Solve RMQ by finding LCA Lowest Common Ancestor - Tarjan's off-line algorithm Flows and related problems Maximum flow - Ford-Fulkerson and Edmonds-Karp Maximum flow - Push-relabel algorithm Maximum flow - Push-relabel algorithm improved Maximum flow - Dinic's algorithm Maximum flow - MPM algorithm Flows with demands Minimum-cost flow Assignment problem. Solution using min-cost-flow in O (N^5)