[go: up one dir, main page]
Scribd
Upload
98 views2 pages

Graph Algorithms Cheat Sheet

This cheat sheet provides an overview of graph algorithms, including types of graphs, representations, and key algorithms for traversals, shortest paths, minimum spanning trees, topological sorting, strongly connected components, and flow/matching. It outlines the complexity of various algorithms and offers problem-solving patterns for different scenarios. Additionally, it includes a complexity reference for common constraints in competitive programming.

Uploaded by

Arya Sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
98 views2 pages

Graph Algorithms Cheat Sheet

This cheat sheet provides an overview of graph algorithms, including types of graphs, representations, and key algorithms for traversals, shortest paths, minimum spanning trees, topological sorting, strongly connected components, and flow/matching. It outlines the complexity of various algorithms and offers problem-solving patterns for different scenarios. Additionally, it includes a complexity reference for common constraints in competitive programming.

Uploaded by

Arya Sharma
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

■ Graph Algorithms Cheat Sheet

1. Graph Basics
Types: Directed / Undirected, Weighted / Unweighted, Cyclic / Acyclic
Representations:
• Adjacency List: O(V+E) space
• Adjacency Matrix: O(V²) space
Terms: Degree, Path, Cycle, Connected Component

2. Traversals
Algorithm Complexity Use Case

DFS O(V+E) Cycle detection, connected components, path finding

BFS O(V+E) Shortest path in unweighted graphs

Multi-source BFS O(V+E) Multiple start points

0–1 BFS O(V+E) Edges with weights 0 or 1

3. Shortest Path Algorithms


Algorithm Complexity Notes

BFS O(V+E) Only unweighted graphs

Dijkstra O((V+E) log V) Non-negative weights, priority queue

Bellman–Ford O(V·E) Handles negative weights, detects cycles

Floyd–Warshall O(V³) All-pairs shortest path

Johnson’s O(V² log V + VE) Sparse graphs, all-pairs shortest path

4. Minimum Spanning Tree (MST)


Algorithm Complexity Notes

Prim’s O(E log V) Good for dense graphs

Kruskal’s O(E log E) Use Union-Find

5. Topological Sort (DAG only)


Algorithm Complexity Notes

DFS-based O(V+E) Recursive

Kahn’s Algorithm O(V+E) Uses in-degree array

6. Strongly Connected Components


Algorithm Complexity Notes

Kosaraju’s O(V+E) Two DFS passes

Tarjan’s O(V+E) Also finds articulation points & bridges

7. Flow & Matching


Algorithm Complexity Notes

Ford–Fulkerson O(E × max_flow) Max flow

Edmonds–Karp O(VE²) BFS version of Ford–Fulkerson

Hopcroft–Karp O(√V·E) Max matching in bipartite graphs

Bipartite Check O(V+E) DFS/BFS 2-coloring

8. Problem-Solving Patterns
• Grid to graph conversion → Treat each cell as a node
• Binary Search + BFS/DFS → For min/max constraints
• Topological Sort + DP → Longest path in DAG
• Bitmask DP on Graphs → TSP & subset problems
• Union-Find → Dynamic connectivity, MST

9. Complexity Reference
V = number of vertices
E = number of edges
Typical bounds for CP:
• O(V+E) → Up to 10■ edges
• O(V²) → Up to 5000 vertices
• O(V³) → Up to 500 vertices

■ Pro Tip:
When stuck: 1. Weighted? → Dijkstra/Bellman-Ford/Floyd-Warshall 2. Unweighted? → BFS 3. DAG? → Topological Sort 4.
Connectivity? → DFS/BFS/Union-Find 5. Flow/Matching? → Ford–Fulkerson/Hopcroft–Karp

You might also like