Graph Algorithms Cheat Sheet
Core graph traversal and shortest-path algorithms — BFS, DFS, Dijkstra — with adjacency list representations and complexity comparisons.
2 PagesIntermediateApr 10, 2026
Graph Representation
Adjacency list representation for weighted and unweighted graphs.
python
from collections import defaultdictgraph = defaultdict(list)graph[0].append(1) # edge 0 -> 1graph[1].append(2)graph[0].append(2)# Weighted graph: store (neighbor, weight) tuplesweighted = defaultdict(list)weighted[0].append((1, 4)) # edge 0->1 with weight 4weighted[1].append((2, 2))
BFS & DFS Traversal
Breadth-first and depth-first traversal using a queue and a stack.
python
from collections import dequedef bfs(graph, start): visited, queue, order = {start}, deque([start]), [] while queue: node = queue.popleft() order.append(node) for neighbor in graph[node]: if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return orderdef dfs(graph, start): visited, stack, order = set(), [start], [] while stack: node = stack.pop() if node not in visited: visited.add(node) order.append(node) stack.extend(graph[node]) return order
Dijkstra's Shortest Path
Single-source shortest paths on a weighted graph using a min-heap.
python
import heapqdef dijkstra(graph, start): dist = {start: 0} pq = [(0, start)] while pq: d, node = heapq.heappop(pq) if d > dist.get(node, float('inf')): continue for neighbor, weight in graph[node]: nd = d + weight if nd < dist.get(neighbor, float('inf')): dist[neighbor] = nd heapq.heappush(pq, (nd, neighbor)) return dist
Algorithm Complexity
Time complexity of common graph algorithms, V = vertices, E = edges.
- BFS / DFS- O(V + E) time, O(V) space; BFS finds shortest path in unweighted graphs
- Dijkstra (binary heap)- O((V + E) log V); requires non-negative edge weights
- Bellman-Ford- O(V * E); slower than Dijkstra but handles negative edge weights and detects negative cycles
- Floyd-Warshall- O(V^3); computes shortest paths between all pairs of vertices
- Kruskal's MST- O(E log E); builds a minimum spanning tree using union-find to avoid cycles
- Prim's MST- O(E log V) with a binary heap; grows the MST one vertex at a time
- Topological Sort- O(V + E); only valid on a directed acyclic graph (DAG)
- A* Search- O(E) with an admissible heuristic; best for single-target pathfinding
Union-Find & Kruskal's MST
Disjoint-set structure with path compression and union by rank, used to build a minimum spanning tree without creating cycles.
python
class DSU: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * n def find(self, x): if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]) # path compression return self.parent[x] def union(self, a, b): ra, rb = self.find(a), self.find(b) if ra == rb: return False if self.rank[ra] < self.rank[rb]: ra, rb = rb, ra self.parent[rb] = ra if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1 return Truedef kruskal(n, edges): dsu = DSU(n) mst_weight = 0 for w, u, v in sorted(edges): # edges as (weight, u, v) if dsu.union(u, v): mst_weight += w return mst_weight
Tarjan's Strongly Connected Components
Single-pass DFS that finds all strongly connected components using discovery times and low-link values.
python
def tarjan_scc(graph, n): index_counter = [0] stack, on_stack = [], [False] * n indices, lowlink = [-1] * n, [0] * n sccs = [] def strongconnect(v): indices[v] = lowlink[v] = index_counter[0] index_counter[0] += 1 stack.append(v) on_stack[v] = True for w in graph[v]: if indices[w] == -1: strongconnect(w) lowlink[v] = min(lowlink[v], lowlink[w]) elif on_stack[w]: lowlink[v] = min(lowlink[v], indices[w]) if lowlink[v] == indices[v]: component = [] while True: w = stack.pop() on_stack[w] = False component.append(w) if w == v: break sccs.append(component) for v in range(n): if indices[v] == -1: strongconnect(v) return sccs
Topological Sort (Kahn's Algorithm)
BFS-based topological ordering using in-degree counting; also detects cycles when fewer than n nodes are output.
python
from collections import dequedef topo_sort(graph, n): in_degree = [0] * n for u in graph: for v in graph[u]: in_degree[v] += 1 queue = deque(u for u in range(n) if in_degree[u] == 0) order = [] while queue: u = queue.popleft() order.append(u) for v in graph[u]: in_degree[v] -= 1 if in_degree[v] == 0: queue.append(v) if len(order) != n: raise ValueError("graph has a cycle, no valid topological order") return order
Advanced Graph Concepts
Structural properties and algorithms beyond basic traversal and shortest paths.
- Bridges & Articulation Points- Found via DFS low-link values; a bridge/cut vertex is an edge/node whose removal disconnects the graph
- Strongly Connected Components (Tarjan/Kosaraju)- Maximal sets of nodes in a directed graph where every node can reach every other node in the set
- 2-SAT- Reduces boolean satisfiability with 2 literals per clause to SCC detection on an implication graph
- Maximum Flow (Ford-Fulkerson / Dinic's)- Finds the max flow through a capacitated network; Dinic's runs in O(V^2 * E) via level graphs and blocking flows
- Lowest Common Ancestor (Binary Lifting)- Precomputes 2^k-th ancestors in O(n log n) to answer LCA queries in O(log n) on a tree
- Bipartite Check- A graph is bipartite iff a BFS/DFS 2-coloring never assigns the same color to adjacent nodes
- Eulerian Path/Circuit- Exists iff the graph is connected and has 0 (circuit) or exactly 2 (path) vertices of odd degree
Bellman-Ford with Negative Cycle Detection
Relaxes all edges V-1 times to compute shortest paths with negative weights, then checks for further relaxation to flag negative cycles.
python
def bellman_ford(n, edges, source): # edges: list of (u, v, weight) dist = [float('inf')] * n dist[source] = 0 for _ in range(n - 1): for u, v, w in edges: if dist[u] != float('inf') and dist[u] + w < dist[v]: dist[v] = dist[u] + w for u, v, w in edges: if dist[u] != float('inf') and dist[u] + w < dist[v]: raise ValueError("graph contains a negative-weight cycle") return dist
Pro Tip
For sparse graphs (E much less than V^2), always prefer an adjacency list over an adjacency matrix — matrices cost O(V^2) memory regardless of edge count and only pay off when the graph is dense.
Was this cheat sheet helpful?
Explore Topics
#GraphAlgorithms#GraphAlgorithmsCheatSheet#Programming#Intermediate#GraphRepresentation#BFSDFSTraversal#DijkstraSShortestPath#AlgorithmComplexity#DataStructures#Algorithms#CheatSheet#SkillVeris
