Introduction
Graphs are versatile data structures used to model relationships and networks. From social networks to road systems, graphs appear in countless real-world applications. This guide covers graph representations, traversal algorithms, and essential graph problems.
Graph Fundamentals
Types of Graphs
Undirected Graph: Directed Graph (Digraph):
A --- B A --> B
/| | /|
/ | | / |
C | D C v
\ | / \ |
\| / \|/
E E
Weighted Graph: Unweighted Graph:
A ---5--- B A --- B
/| | /| |
2/ |7 |3 / | |
/ | \ / / | |
C 1 D 4 E C D E
- Directed vs Undirected: Edges have direction or not
- Weighted vs Unweighted: Edges have costs or equal weight
- Cyclic vs Acyclic: Contains cycles or not
- Connected vs Disconnected: All nodes reachable or not
Graph Representations
# 1. Adjacency Matrix
# Good for dense graphs, O(1) edge lookup
#
# A B C D
# A 0 1 1 0
# B 1 0 0 1
# C 1 0 0 1
# D 0 1 1 0
class AdjacencyMatrix:
def __init__(self, n):
self.n = n
self.matrix = [[0] * n for _ in range(n)]
def add_edge(self, i, j, weight=1):
self.matrix[i][j] = weight
self.matrix[j][i] = weight # Undirected
# 2. Adjacency List
# Good for sparse graphs, O(1) iteration of neighbors
#
# A: [B, C]
# B: [A, D]
# C: [A, D]
# D: [B, C]
class AdjacencyList:
def __init__(self):
self.graph = {}
def add_edge(self, u, v, weight=1):
if u not in self.graph:
self.graph[u] = []
if v not in self.graph:
self.graph[v] = []
self.graph[u].append((v, weight))
self.graph[v].append((u, weight)) # Undirected
def get_neighbors(self, u):
return self.graph.get(u, [])
# 3. Edge List
# Simple, good for Kruskal's algorithm
# [(A, B, 1), (B, C, 2), (C, D, 3)]
class EdgeList:
def __init__(self):
self.edges = []
def add_edge(self, u, v, weight=1):
self.edges.append((weight, u, v))
Graph Traversal
Breadth-First Search (BFS)
BFS explores level by level, using a queue. Perfect for finding shortest path in unweighted graphs.
from collections import deque
def bfs(graph, start):
"""Breadth-First Search - finds shortest path in unweighted graph."""
visited = set()
queue = deque([start])
visited.add(start)
result = []
while queue:
vertex = queue.popleft()
result.append(vertex)
for neighbor in graph.get(vertex, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0] # For weighted graphs
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
def bfs_with_levels(graph, start):
"""BFS tracking level/depth of each node."""
visited = {start: 0}
queue = deque([start])
level_map = {}
while queue:
vertex = queue.popleft()
level = visited[vertex]
if level not in level_map:
level_map[level] = []
level_map[level].append(vertex)
for neighbor in graph.get(vertex, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
if neighbor not in visited:
visited[neighbor] = level + 1
queue.append(neighbor)
return level_map
# Example: Shortest path in unweighted graph
def shortest_path(graph, start, end):
"""Find shortest path between start and end."""
if start == end:
return [start]
visited = {start}
queue = deque([(start, [start])])
while queue:
vertex, path = queue.popleft()
for neighbor in graph.get(vertex, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
if neighbor == end:
return path + [neighbor]
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, path + [neighbor]))
return None # No path exists
# Test
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'],
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']
}
print(bfs(graph, 'A')) # ['A', 'B', 'C', 'D', 'E', 'F']
print(shortest_path(graph, 'A', 'F')) # ['A', 'C', 'F'] or ['A', 'B', 'E', 'F']
Depth-First Search (DFS)
DFS explores as far as possible before backtracking, using recursion or a stack.
def dfs_recursive(graph, start, visited=None):
"""Recursive DFS."""
if visited is None:
visited = set()
visited.add(start)
result = [start]
for neighbor in graph.get(start, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
if neighbor not in visited:
result.extend(dfs_recursive(graph, neighbor, visited))
return result
def dfs_iterative(graph, start):
"""Iterative DFS using stack."""
visited = set()
stack = [start]
result = []
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
result.append(vertex)
# Add neighbors in reverse order for consistent ordering
neighbors = graph.get(vertex, [])
if isinstance(neighbors[0], tuple):
neighbors = [n[0] for n in neighbors]
for neighbor in reversed(neighbors):
if neighbor not in visited:
stack.append(neighbor)
return result
# DFS for path finding
def dfs_find_path(graph, start, end, visited=None, path=None):
"""Find any path from start to end using DFS."""
if visited is None:
visited = set()
if path is None:
path = []
visited.add(start)
path.append(start)
if start == end:
return path[:]
for neighbor in graph.get(start, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
if neighbor not in visited:
result = dfs_find_path(graph, neighbor, end, visited, path)
if result:
return result
path.pop()
return None
# Cycle detection using DFS
def has_cycle(graph):
"""Detect if directed graph has a cycle."""
visited = set()
rec_stack = set()
def dfs(node):
visited.add(node)
rec_stack.add(node)
for neighbor in graph.get(node, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
if neighbor not in visited:
if dfs(neighbor):
return True
elif neighbor in rec_stack:
return True
rec_stack.remove(node)
return False
for node in graph:
if node not in visited:
if dfs(node):
return True
return False
# Test
print(dfs_recursive(graph, 'A')) # ['A', 'B', 'D', 'E', 'F', 'C']
print(has_cycle({'A': ['B'], 'B': ['C'], 'C': ['A']})) # True
Essential Graph Algorithms
Topological Sort
Ordering vertices in a DAG such that for every edge (u, v), u comes before v.
def topological_sort(graph):
"""Kahn's Algorithm for topological sort."""
in_degree = {node: 0 for node in graph}
for node in graph:
for neighbor in graph[node]:
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
in_degree[neighbor] = in_degree.get(neighbor, 0) + 1
queue = [node for node in in_degree if in_degree[node] == 0]
result = []
while queue:
node = queue.pop(0)
result.append(node)
for neighbor in graph.get(node, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(result) != len(graph):
return None # Cycle detected
return result
def topological_sort_dfs(graph):
"""DFS-based topological sort."""
visited = set()
stack = []
def dfs(node):
visited.add(node)
for neighbor in graph.get(node, []):
if isinstance(neighbor, tuple):
neighbor = neighbor[0]
if neighbor not in visited:
dfs(neighbor)
stack.append(node)
for node in graph:
if node not in visited:
dfs(node)
return stack[::-1]
# Example: Course scheduling
# Prerequisites: {'CSC300': ['CSC200'], 'CSC200': ['CSC100'], 'CSC100': []}
courses = {
'CSC100': [],
'CSC200': ['CSC100'],
'CSC300': ['CSC200'],
'MATH101': [],
'MATH201': ['MATH101']
}
print(topological_sort(courses)) # ['MATH101', 'MATH201', 'CSC100', 'CSC200', 'CSC300']
Dijkstra’s Algorithm
Finds shortest path in weighted graphs with non-negative weights.
import heapq
def dijkstra(graph, start, end=None):
"""
Dijkstra's algorithm for shortest path.
Time: O((V + E) log V) using min-heap
Works only with non-negative edge weights.
"""
distances = {node: float('inf') for node in graph}
distances[start] = 0
previous = {node: None for node in graph}
# Priority queue: (distance, node)
pq = [(0, start)]
visited = set()
while pq:
current_dist, current = heapq.heappop(pq)
if current in visited:
continue
visited.add(current)
if end and current == end:
break
for neighbor in graph.get(current, []):
if isinstance(neighbor, tuple):
neighbor, weight = neighbor
else:
weight = 1
if neighbor in visited:
continue
new_dist = current_dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
previous[neighbor] = current
heapq.heappush(pq, (new_dist, neighbor))
# Reconstruct path
path = []
current = end
while current:
path.append(current)
current = previous[current]
return distances, path[::-1] if path and path[0] == start else []
# Example: Road network
road_network = {
'A': [('B', 4), ('C', 2)],
'B': [('A', 4), ('C', 1), ('D', 5)],
'C': [('A', 2), ('B', 1), ('D', 8)],
'D': [('B', 5), ('C', 8)]
}
distances, path = dijkstra(road_network, 'A', 'D')
print(f"Shortest distance: {distances['D']}") # 5
print(f"Path: {' -> '.join(path)}") # A -> B -> C -> D
Union-Find (Disjoint Set Union)
Data structure for tracking connected components.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
"""Path compression."""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
"""Union by rank."""
px, py = self.find(x), self.find(y)
if px == py:
return False
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
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# Number of connected components
def count_components(edges, n):
uf = UnionFind(n)
for u, v in edges:
uf.union(u, v)
return len(set(uf.find(i) for i in range(n)))
Minimum Spanning Tree (Kruskal’s Algorithm)
def kruskal_mst(n, edges):
"""
Kruskal's algorithm for MST.
edges: list of (weight, u, v)
"""
# Sort edges by weight
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
# Example
edges = [
(1, 0, 1),
(2, 0, 2),
(3, 1, 2),
(4, 1, 3),
(5, 2, 3)
]
mst, weight = kruskal_mst(4, edges)
print(f"MST edges: {mst}")
print(f"Total weight: {weight}")
Common Interview Patterns
1. Island Counting
def num_islands(grid):
"""Count number of islands in a grid."""
if not grid:
return 0
rows, cols = len(grid), len(grid[0])
visited = set()
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
def dfs(r, c):
if (r, c) in visited or r < 0 or r >= rows or c < 0 or c >= cols:
return
if grid[r][c] == '0':
return
visited.add((r, c))
for dr, dc in directions:
dfs(r + dr, c + dc)
count = 0
for r in range(rows):
for c in range(cols):
if (r, c) not in visited and grid[r][c] == '1':
dfs(r, c)
count += 1
return count
2. Clone Graph
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def clone_graph(node):
"""Deep copy a graph."""
if not node:
return None
visited = {}
def dfs(original):
if original in visited:
return visited[original]
clone = Node(original.val)
visited[original] = clone
for neighbor in original.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
3. Word Ladder
def word_ladder(begin, end, word_list):
"""Find shortest transformation sequence."""
word_set = set(word_list)
if end not in word_set:
return 0
queue = deque([(begin, 1)])
visited = {begin}
while queue:
word, level = queue.popleft()
if word == end:
return level
# Try all possible single character transformations
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + c + word[i+1:]
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, level + 1))
return 0
Time Complexity Summary
| Algorithm | Time | Space | Use Case |
|---|---|---|---|
| BFS | O(V + E) | O(V) | Shortest path (unweighted) |
| DFS | O(V + E) | O(V) | Cycle detection, topological sort |
| Dijkstra | O(E log V) | O(V) | Shortest path (weighted) |
| Kruskal | O(E log E) | O(V) | MST |
| Topological | O(V + E) | O(V) | DAG ordering |
Conclusion
Graphs are fundamental data structures with numerous applications. Master these algorithms and patterns to confidently tackle graph problems in interviews and real-world applications.
Comments