Graph Representations
# Adjacency List (most common for sparse graphs)
graph_directed = {
0: [1, 2],
1: [3],
2: [3, 4],
3: [5],
4: [5],
5: []
}
# Weighted adjacency list
weighted_graph = {
'A': [('B', 4), ('C', 2)],
'B': [('D', 5)],
'C': [('B', 1), ('D', 8)],
'D': []
}
# Adjacency Matrix (for dense graphs, O(1) edge lookup)
# matrix[i][j] = weight (0 = no edge)
matrix = [
[0, 1, 1, 0],
[0, 0, 0, 1],
[0, 0, 0, 1],
[0, 0, 0, 0],
]
# Edge list (for algorithms like Kruskal's)
edges = [(0, 1, 4), (0, 2, 2), (1, 3, 5), (2, 3, 8)] # (u, v, weight)
BFS — Breadth-First Search
from collections import deque
def bfs(graph, start):
"""O(V + E)"""
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
# BFS for shortest path in unweighted graph
def shortest_path_bfs(graph, start, end):
if start == end:
return [start]
visited = {start}
queue = deque([(start, [start])])
while queue:
node, path = queue.popleft()
for neighbor in graph.get(node, []):
if neighbor == end:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # no path
DFS — Depth-First Search
def dfs_recursive(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph.get(start, []):
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
def dfs_iterative(graph, start):
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
for neighbor in reversed(graph.get(node, [])):
if neighbor not in visited:
stack.append(neighbor)
return result
Cycle Detection
def has_cycle_directed(graph):
"""DFS with coloring: white=0, gray=1, black=2"""
color = {node: 0 for node in graph}
def dfs(node):
color[node] = 1 # processing
for neighbor in graph.get(node, []):
if color[neighbor] == 1:
return True # back edge = cycle
if color[neighbor] == 0 and dfs(neighbor):
return True
color[node] = 2 # done
return False
return any(dfs(node) for node in graph if color[node] == 0)
def has_cycle_undirected(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True # back edge to non-parent
return False
return any(dfs(node, -1) for node in graph if node not in visited)
Topological Sort
from collections import deque
def topological_sort_kahn(graph, in_degree):
"""Kahn's algorithm (BFS-based) — O(V + E)"""
queue = deque(node for node in in_degree if in_degree[node] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph.get(node, []):
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) != len(in_degree):
return None # cycle detected
return order
# Course Schedule example
def can_finish(num_courses, prerequisites):
graph = {i: [] for i in range(num_courses)}
in_deg = {i: 0 for i in range(num_courses)}
for course, prereq in prerequisites:
graph[prereq].append(course)
in_deg[course] += 1
topo = topological_sort_kahn(graph, in_deg)
return topo is not None and len(topo) == num_courses
print(can_finish(4, [[1,0],[2,1],[3,2]])) # True
print(can_finish(2, [[0,1],[1,0]])) # False (cycle)
Dijkstra's Algorithm
import heapq
def dijkstra(graph, start):
"""Shortest paths from start to all nodes — O((V+E) log V)"""
dist = {node: float('inf') for node in graph}
dist[start] = 0
prev = {node: None for node in graph}
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue # outdated entry
for v, weight in graph.get(u, []):
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
prev[v] = u
heapq.heappush(pq, (dist[v], v))
return dist, prev
def reconstruct_path(prev, start, end):
path = []
curr = end
while curr is not None:
path.append(curr)
curr = prev[curr]
return path[::-1] if path[-1] == start else []
# Example
graph = {
'A': [('B', 4), ('C', 2)],
'B': [('D', 5), ('C', 1)],
'C': [('B', 1), ('D', 8)],
'D': []
}
dist, prev = dijkstra(graph, 'A')
print(dist) # {'A': 0, 'B': 3, 'C': 2, 'D': 8}
print(reconstruct_path(prev, 'A', 'D')) # ['A', 'C', 'B', 'D']
Union-Find (Disjoint Set Union)
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = 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, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False # already in same component
# Union by rank
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.components -= 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# Minimum Spanning Tree — Kruskal's Algorithm
def kruskal_mst(n, edges):
"""edges: [(weight, u, v)]"""
edges.sort()
uf = UnionFind(n)
mst = []
total_weight = 0
for weight, u, v in edges:
if uf.union(u, v):
mst.append((u, v, weight))
total_weight += weight
if len(mst) == n - 1:
break
return mst, total_weight
edges = [(4, 0, 1), (2, 0, 2), (1, 1, 2), (5, 1, 3), (8, 2, 3)]
mst, cost = kruskal_mst(4, edges)
print(mst) # [(0,2,2), (1,2,1), (1,3,5)] or similar
print(cost) # 8
Exercises
Exercise 1: Number of Islands
Count distinct islands in a 2D grid (DFS/BFS).
Solution:
def num_islands(grid):
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
count = 0
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != '1':
return
grid[r][c] = '0' # mark visited
dfs(r+1, c); dfs(r-1, c)
dfs(r, c+1); dfs(r, c-1)
for r in range(rows):
for c in range(cols):
if grid[r][c] == '1':
dfs(r, c)
count += 1
return count
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
print(num_islands(grid)) # 3
Exercise 2: Word Ladder
Find shortest transformation sequence from beginWord to endWord.
Solution:
from collections import deque
def word_ladder(begin, end, word_list):
word_set = set(word_list)
if end not in word_set:
return 0
queue = deque([(begin, 1)])
visited = {begin}
while queue:
word, length = queue.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word == end:
return length + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, length + 1))
return 0
print(word_ladder("hit", "cog", ["hot","dot","dog","lot","log","cog"]))
# 5 (hit → hot → dot → dog → cog)