Graphs model anything with connections — networks, maps, dependencies. Learn to represent them, traverse with BFS and DFS, find shortest paths with Dijkstra and Bellman-Ford, and connect components with Union-Find.
A graph is nodes (vertices) joined by edges, which may be directed or undirected, weighted or not. The usual representation is an adjacency list — a map from each node to its neighbors — which is memory-efficient for the sparse graphs common in practice. An adjacency matrix (a 2D grid of edges) is simpler but uses O(V²) space, worthwhile only for dense graphs.
# adjacency list: node -> its neighbors (the common, memory-efficient choice)
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C"],
}
# directed graph: edges go one way (A->B doesn't imply B->A)
# weighted graph: store (neighbor, weight) pairs, e.g. "A": [("B", 5), ("C", 2)]
# adjacency MATRIX alternative: grid[i][j] = 1 if edge i->j.
# O(V^2) space -> only worth it for DENSE graphs. Lists win for sparse ones.The two fundamental graph traversals mirror the tree ones. Breadth-first search explores level by level with a queue and finds the shortest path in an unweighted graph. Depth-first search plunges down each branch with recursion or a stack and suits cycle detection, topological sorting, and connectivity. Both are O(V + E) and must track visited nodes to avoid infinite loops on cycles.
from collections import deque
def bfs(graph, start): # shortest path in UNWEIGHTED graphs
visited, q = {start}, deque([start])
while q:
node = q.popleft() # queue -> explore nearest first
for nb in graph[node]:
if nb not in visited:
visited.add(nb) # mark on enqueue to avoid re-visiting
q.append(nb)
return visited
def dfs(graph, node, visited=None): # go deep; cycles, topo-sort, components
if visited is None: visited = set()
visited.add(node)
for nb in graph[node]:
if nb not in visited:
dfs(graph, nb, visited)
return visited
# both O(V + E). The 'visited' set is essential — without it, cycles loop forever.When edges have non-negative weights, Dijkstra’s algorithm finds the shortest path from a source to every node. It greedily expands the closest unfinalized node using a min-heap (priority queue), settling each node once. It runs in O(E log V) and is the workhorse behind routing and maps. For graphs with negative edges, Dijkstra breaks and you need Bellman-Ford.
import heapq
def dijkstra(graph, start): # graph: node -> [(neighbor, weight)]
dist = {start: 0}
pq = [(0, start)] # (distance so far, node) min-heap
while pq:
d, node = heapq.heappop(pq) # always expand the CLOSEST node
if d > dist.get(node, float("inf")):
continue # stale entry, skip
for nb, w in graph[node]:
nd = d + w
if nd < dist.get(nb, float("inf")):
dist[nb] = nd # found a shorter route to nb
heapq.heappush(pq, (nd, nb))
return dist
# O(E log V). Requires NON-NEGATIVE weights. Negative edges -> Bellman-Ford.Two shortest-path variants complete the picture. Bellman-Ford handles negative edge weights and can detect negative cycles by relaxing every edge V−1 times, at a slower O(V·E). A* speeds up Dijkstra toward a specific target by adding a heuristic estimate of remaining distance, guiding the search — the standard for game pathfinding and maps. Knowing which to reach for is the point.
Which shortest-path algorithm?
Dijkstra non-negative weights, all destinations O(E log V) fast
Bellman-Ford handles NEGATIVE weights; detects O(V*E) slower
negative cycles (relax all edges V-1 times)
A* (A-star) Dijkstra + a heuristic estimating guided fastest
distance-to-goal; aims at ONE target to target
-> game pathfinding, maps
Rule of thumb:
weights >= 0, want all nodes -> Dijkstra
negative weights possible -> Bellman-Ford
one target + a good heuristic -> A*Union-Find (disjoint-set) tracks which nodes belong to the same group with near-O(1) union and find operations, making it ideal for connectivity questions and cycle detection. It powers Kruskal’s algorithm for the minimum spanning tree — the cheapest set of edges connecting every node — by adding edges cheapest-first and skipping any that would form a cycle. Prim’s algorithm builds the same tree by growing outward with a heap.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
def find(self, x): # which group is x in?
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, a, b): # merge two groups; False if already joined
ra, rb = self.find(a), self.find(b)
if ra == rb: return False
self.parent[ra] = rb
return True
# Kruskal's MST: sort edges by weight, add each unless it forms a cycle
def kruskal(n, edges): # edges: (weight, u, v)
uf, mst = UnionFind(n), []
for w, u, v in sorted(edges):
if uf.union(u, v): # union returns False on a cycle -> skip
mst.append((u, v, w))
return mst # Prim's builds the same MST with a heap