🌍 Real-world use — this exact structure models road maps, social-network friend lists, web-page links, computer networks, molecule bonds, and project task dependencies.
3 / 20
1. Breadth-First Search (BFS)
What it does. Explores a graph layer by layer from a start vertex, so it finds the path with the fewest edges to every reachable vertex. The first time BFS reaches a vertex, it has found a shortest (hop-count) route to it.
Python — BFS shortest (unweighted) pathfrom collections import deque
def bfs(G, s):
"""Distances and parents from source s."""
dist, parent = {s: 0}, {s: None}
q = deque([s])
while q:
u = q.popleft()
for v in G[u]:
if v not in dist: # first time seen = shortest
dist[v] = dist[u] + 1
parent[v] = u
q.append(v)
return dist, parent
def shortest_path(G, s, t):
dist, parent = bfs(G, s)
if t not in dist:
return None # unreachable
path = []
while t is not None:
path.append(t); t = parent[t]
return path[::-1]
Cost. $O(n + m)$ — linear in vertices + edges.
🌍 Real-world use — "degrees of separation" between two people on Facebook/LinkedIn; GPS routes with the fewest changes; web crawlers exploring links level by level; broadcasting a message across a network; solving mazes and puzzles like word ladders or a Rubik's cube in the fewest moves.
What it does. Dives as deep as possible before backtracking. Perfect for fully exploring a region, listing everything reachable, and splitting a graph into its separate clusters (connected components).
Python — DFS & connected componentsdef dfs(G, s):
"""Set of all vertices reachable from s (iterative)."""
seen, stack = set(), [s]
while stack:
u = stack.pop()
if u not in seen:
seen.add(u)
stack.extend(v for v in G[u] if v not in seen)
return seen
def connected_components(G):
"""List of clusters; each is a set of vertices."""
seen, comps = set(), []
for v in G:
if v not in seen:
cluster = dfs(G, v)
comps.append(cluster)
seen |= cluster
return comps
🌍 Real-world use — finding friend groups or communities in a social graph; the "flood fill" / paint-bucket tool in image editors; maze generation; garbage collectors marking which objects are still reachable in memory; detecting isolated sub-networks after a failure.
5 / 20
3. Cycle detection
What it does. Decides whether the graph contains a loop. For an undirected graph, a DFS that meets an already-visited vertex (other than the one it just came from) has found a cycle.
Python — undirected cycle detectiondef has_cycle(G):
seen = set()
def visit(u, parent):
seen.add(u)
for v in G[u]:
if v not in seen:
if visit(v, u):
return True
elif v != parent: # back-edge = cycle
return True
return False
return any(visit(v, None) for v in G if v not in seen)
🌍 Real-world use — spotting deadlocks in operating systems (processes waiting on each other in a circle); catching circular dependencies in package managers (npm, pip) and build systems; detecting circular references in spreadsheets; finding loops in financial transaction chains.
6 / 20
4. Topological sort (ordering with prerequisites)
What it does. Given a directed acyclic graph of "X must come before Y" constraints, it produces a valid linear order respecting all of them. Kahn's algorithm repeatedly removes a vertex with no remaining prerequisites.
Python — Kahn's algorithmfrom collections import deque
def topo_sort(G):
"""G: vertex -> list of successors. Returns an order, or None if cyclic."""
indeg = {u: 0 for u in G}
for u in G:
for v in G[u]:
indeg[v] = indeg.get(v, 0) + 1
for u in G:
indeg.setdefault(u, 0)
q = deque([u for u in indeg if indeg[u] == 0])
order = []
while q:
u = q.popleft()
order.append(u)
for v in G.get(u, ()):
indeg[v] -= 1
if indeg[v] == 0:
q.append(v)
return order if len(order) == len(indeg) else None
🌍 Real-world use — build systems compiling files in dependency order (Make, Gradle, npm); scheduling tasks/jobs that depend on one another; planning a degree's courses around prerequisites; the order a spreadsheet recalculates cells; resolving install order for software packages.
7 / 20
5. Bipartite check (two-coloring)
What it does. Tests whether the vertices split into two groups so that every edge crosses between groups — i.e. the graph is 2-colorable. BFS alternates colors; a clash means it is impossible.
Python — 2-coloring / bipartite testfrom collections import deque
def two_color(G):
"""Returns {vertex: 0/1} if bipartite, else None."""
color = {}
for s in G:
if s in color:
continue
color[s] = 0
q = deque([s])
while q:
u = q.popleft()
for v in G[u]:
if v not in color:
color[v] = 1 - color[u]
q.append(v)
elif color[v] == color[u]:
return None # odd cycle = not bipartite
return color
🌍 Real-world use — matching two kinds of things — job applicants to positions, students to schools, riders to drivers; modeling user–item interactions for recommendations; checking whether a conflict graph can be split into two shifts/rooms with no clashes.
8 / 20
6. Dijkstra — cheapest weighted path
What it does. Finds the lowest-cost route from a source to all vertices when edge weights are non-negative. A priority queue always expands the closest unsettled vertex next.
Python — Dijkstra with a heapimport heapq
def dijkstra(G, s):
"""G weighted (G[u] = {v: w}). Returns shortest distances from s."""
dist = {s: 0}
pq = [(0, s)]
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float("inf")):
continue # stale entry
for v, w in G[u].items():
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist
Cost. $O((n + m)\log n)$ with a binary heap.
🌍 Real-world use — GPS navigation (Google Maps, Waze) computing fastest/shortest routes; internet packet routing (OSPF protocol); cheapest multi-leg flight or shipping itineraries; least-cost paths in games on weighted terrain.
9 / 20
7. Bellman–Ford — paths with negative weights
What it does. Like Dijkstra, but tolerates negative edge weights and, as a bonus, detects negative cycles. It simply relaxes every edge $n-1$ times.
Python — Bellman–Forddef bellman_ford(G, s):
"""G weighted (G[u] = {v: w}). Raises if a negative cycle exists."""
dist = {v: float("inf") for v in G}
dist[s] = 0
edges = [(u, v, w) for u in G for v, w in G[u].items()]
for _ in range(len(G) - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges: # one more pass = cycle check
if dist[u] + w < dist[v]:
raise ValueError("Negative cycle detected!")
return dist
Cost. $O(n \cdot m)$.
🌍 Real-world use — detecting currency-exchange arbitrage (a negative cycle means free profit); distance-vector internet routing (the classic RIP protocol); any optimization where edges can represent gains as well as costs.
10 / 20
8. Floyd–Warshall — distance between every pair
What it does. Computes the shortest distance between all pairs of vertices at once, by asking "is going through vertex $k$ a shortcut?" for every $k$.
Python — Floyd–Warshalldef floyd_warshall(G):
nodes = list(G)
idx = {v: i for i, v in enumerate(nodes)}
n = len(nodes)
d = [[float("inf")] * n for _ in range(n)]
for i in range(n):
d[i][i] = 0
for u in G:
for v, w in G[u].items():
d[idx[u]][idx[v]] = w
for k in range(n): # try every intermediate vertex
for i in range(n):
for j in range(n):
if d[i][k] + d[k][j] < d[i][j]:
d[i][j] = d[i][k] + d[k][j]
return nodes, d
Cost. $O(n^3)$ — best for small, dense graphs.
🌍 Real-world use — precomputing a full distance table for a small road or transit network; building routing tables; measuring "closeness" of everyone in a social network; computing the transitive closure (who can reach whom).
11 / 20
9. Minimum Spanning Tree — Kruskal
What it does. Connects all vertices with the smallest possible total edge weight. Kruskal sorts edges cheapest-first and adds an edge whenever it joins two still-separate pieces (Union-Find avoids creating a cycle).
Python — Kruskal with Union-Finddef kruskal(G):
"""G weighted (G[u] = {v: w}). Returns the MST as a list of edges."""
parent = {v: v for v in G}
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]] # path compression
x = parent[x]
return x
def union(x, y):
rx, ry = find(x), find(y)
if rx == ry:
return False
parent[rx] = ry
return True
edges = sorted((w, u, v) for u in G for v, w in G[u].items() if u < v)
mst = []
for w, u, v in edges:
if union(u, v):
mst.append((u, v, w))
if len(mst) == len(G) - 1:
break
return mst
🌍 Real-world use — laying the cheapest network of fiber, electrical grid, water pipes or roads that still connects every site; clustering data points; image segmentation; approximate solutions to the travelling-salesman problem.
12 / 20
10. Minimum Spanning Tree — Prim
What it does. Solves the same minimum-cost-network problem, but grows the tree outward from one seed vertex, always grabbing the cheapest edge that reaches a new vertex (via a heap). Often preferred on dense graphs.
Python — Prim with a heapimport heapq
def prim(G, start=None):
if start is None:
start = next(iter(G))
in_tree = {start}
mst = []
heap = [(w, start, v) for v, w in G[start].items()]
heapq.heapify(heap)
while heap and len(in_tree) < len(G):
w, u, v = heapq.heappop(heap)
if v in in_tree:
continue
in_tree.add(v)
mst.append((u, v, w))
for x, wx in G[v].items():
if x not in in_tree:
heapq.heappush(heap, (wx, v, x))
return mst
🌍 Real-world use — same applications as Kruskal — telecom/utility network design, circuit board wiring, cluster analysis — and it is the natural choice when the network is dense or you want to grow it incrementally from a hub.
13 / 20
11. Greedy coloring — conflict-free assignment
What it does. Assigns each vertex the smallest "color" (label) not used by its neighbors. Colors stand for time slots, frequencies, rooms, or registers — adjacent vertices (which conflict) always get different ones.
Python — greedy coloring (largest-degree first)def greedy_coloring(G, order=None):
if order is None: # Welsh-Powell: high degree first
order = sorted(G, key=lambda v: len(G[v]), reverse=True)
color = {}
for v in order:
used = {color[u] for u in G[v] if u in color}
c = 0
while c in used:
c += 1
color[v] = c
return color # max(color.values())+1 = #labels
🌍 Real-world use — building exam/class timetables so conflicting events never overlap; assigning radio/Wi-Fi frequencies to towers so neighbors don't interfere; register allocation inside a compiler; scheduling sports leagues; Sudoku-style constraint solving.
14 / 20
12. PageRank — ranking importance
What it does. Scores how "important" each vertex is, based on the idea that important vertices are pointed to by other important vertices. It simulates a random surfer following links, with a small chance of jumping anywhere.
Python — iterative PageRankdef pagerank(G, damping=0.85, iterations=100):
"""G directed (G[u] = list of pages u links to)."""
N = len(G)
pr = {v: 1 / N for v in G}
out = {v: len(G[v]) for v in G}
for _ in range(iterations):
new = {}
for v in G:
incoming = sum(pr[u] / out[u]
for u in G if v in G[u] and out[u] > 0)
new[v] = (1 - damping) / N + damping * incoming
pr = new
return pr # higher = more important
🌍 Real-world use — the algorithm that launched Google Search — ranking web pages by link importance; ranking influential papers in citation networks; finding key influencers in social media; recommendation and fraud-detection systems.
15 / 20
13. A* search — guided pathfinding
What it does. A smarter Dijkstra: it adds a heuristic estimate of the remaining distance to the goal, so it heads toward the target instead of expanding in all directions. With an admissible heuristic it still returns the optimal path, usually much faster.
Python — A* searchimport heapq
def a_star(G, start, goal, h):
"""G weighted (G[u] = {v: w}); h(v) estimates distance v -> goal."""
open_pq = [(h(start), 0, start)]
g = {start: 0}
parent = {start: None}
while open_pq:
_, gu, u = heapq.heappop(open_pq)
if u == goal:
path = []
while u is not None:
path.append(u); u = parent[u]
return path[::-1], g[goal]
if gu > g.get(u, float("inf")):
continue
for v, w in G[u].items():
ng = gu + w
if ng < g.get(v, float("inf")):
g[v] = ng; parent[v] = u
heapq.heappush(open_pq, (ng + h(v), ng, v))
return None, float("inf")
🌍 Real-world use — character and unit pathfinding in video games; robot and drone motion planning; GPS routing with a straight-line distance heuristic to stay fast on huge maps.
16 / 20
Where each algorithm lives — a field guide
Domain
Algorithms at work
Maps & navigation
BFS, Dijkstra, A*, Floyd–Warshall
Social networks
BFS (degrees of separation), DFS (communities), PageRank (influence)