Graph Algorithms Cheat Sheet

Graphs are everywhere in interviews. This cheat sheet covers all essential algorithms.

Graph Representations

• Adjacency List (most common)
• Adjacency Matrix
• Edge List

Core Algorithms

DFS (Depth-First Search)

Use for: Cycle detection, topological sort, connected components

BFS (Breadth-First Search)

Use for: Shortest path, level-order traversal

Dijkstra's Algorithm

Use for: Shortest path with weighted edges

Union Find

Use for: Connected components, cycle detection

Common Patterns

• Number of Islands
• Course Schedule
• Clone Graph
• Word Ladder

Time Complexities

• DFS/BFS: O(V + E)
• Dijkstra's: O((V + E) log V)
• Union Find: O(α(n)) ≈ O(1)

Keep this cheat sheet handy for your interviews!