Adjacency List
Graph representation using adjacency lists. Compare with adjacency matrix and understand space-time tradeoffs.
While matrices represent graphs as 2D grids, general graphs use adjacency lists: each vertex stores a list of its neighbors. This representation is more flexible and efficient for most real-world graphs.
Adjacency List Basics
# Graph:
# 0 --- 1
# | / |
# | / |
# | / |
# 2 --- 3
# Adjacency list representation:
graph = {
0: [1, 2],
1: [0, 2, 3],
2: [0, 1, 3],
3: [1, 2]
}
Building Adjacency Lists
From Edge List
def build_graph(n, edges, directed=False):
graph = [[] for _ in range(n)]
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (2, 3)]
graph = build_graph(4, edges)
# graph[0] = [1, 2]
# graph[1] = [0, 2, 3]
# graph[2] = [0, 1, 3]
# graph[3] = [1, 2]
With Dictionary (Flexible Vertex Names)
from collections import defaultdict
def build_graph_dict(edges, directed=False):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
if not directed:
graph[v].append(u)
return graph
edges = [('A', 'B'), ('A', 'C'), ('B', 'C')]
graph = build_graph_dict(edges)
# graph['A'] = ['B', 'C']
# graph['B'] = ['A', 'C']
# graph['C'] = ['A', 'B']
With Weights
def build_weighted_graph(n, edges, directed=False):
graph = [[] for _ in range(n)]
for u, v, weight in edges:
graph[u].append((v, weight))
if not directed:
graph[v].append((u, weight))
return graph
edges = [(0, 1, 5), (0, 2, 3), (1, 2, 2)]
graph = build_weighted_graph(3, edges)
# graph[0] = [(1, 5), (2, 3)]
# graph[1] = [(0, 5), (2, 2)]
# graph[2] = [(0, 3), (1, 2)]
DFS on Adjacency List
use std::collections::HashSet;
fn dfs(graph: &[Vec<usize>], start: usize) -> Vec<usize> {
let mut visited = HashSet::new();
let mut result = Vec::new();
fn explore(graph: &[Vec<usize>], node: usize, visited: &mut HashSet<usize>,
result: &mut Vec<usize>) {
if visited.contains(&node) {
return;
}
visited.insert(node);
result.push(node);
for &neighbor in &graph[node] {
explore(graph, neighbor, visited, result);
}
}
explore(graph, start, &mut visited, &mut result);
result
}
// Iterative version
fn dfs_iterative(graph: &[Vec<usize>], start: usize) -> Vec<usize> {
let mut visited = HashSet::new();
let mut stack = vec![start];
let mut result = Vec::new();
while let Some(node) = stack.pop() {
if visited.contains(&node) {
continue;
}
visited.insert(node);
result.push(node);
for &neighbor in graph[node].iter().rev() {
if !visited.contains(&neighbor) {
stack.push(neighbor);
}
}
}
result
}
BFS on Adjacency List
use std::collections::{HashSet, VecDeque};
fn bfs(graph: &[Vec<usize>], start: usize) -> Vec<usize> {
let mut visited = HashSet::new();
let mut queue = VecDeque::new();
let mut result = Vec::new();
visited.insert(start);
queue.push_back(start);
while let Some(node) = queue.pop_front() {
result.push(node);
for &neighbor in &graph[node] {
if !visited.contains(&neighbor) {
visited.insert(neighbor);
queue.push_back(neighbor);
}
}
}
result
}
Visited Timing
In BFS, mark nodes as visited when adding to queue (not when processing). This prevents adding the same node multiple times, improving efficiency.
Problem: Find All Paths
Find all paths between two nodes:
def find_all_paths(graph, start, end):
paths = []
current_path = []
def dfs(node):
current_path.append(node)
if node == end:
paths.append(current_path.copy())
else:
for neighbor in graph[node]:
if neighbor not in current_path: # Avoid cycles
dfs(neighbor)
current_path.pop()
dfs(start)
return paths
graph = [[1, 2], [2, 3], [3], []] # DAG: 0→1→2→3, 0→2→3
print(find_all_paths(graph, 0, 3)) # [[0, 1, 2, 3], [0, 1, 3], [0, 2, 3]]
Problem: Detect Cycle (Undirected)
def has_cycle_undirected(graph):
visited = set()
def dfs(node, parent):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
if dfs(neighbor, node):
return True
elif neighbor != parent:
return True # Cycle found
return False
# Check all components
for node in range(len(graph)):
if node not in visited:
if dfs(node, -1):
return True
return False
Problem: Detect Cycle (Directed)
def has_cycle_directed(graph):
# 0: unvisited, 1: in current path, 2: done
state = [0] * len(graph)
def dfs(node):
state[node] = 1 # In current path
for neighbor in graph[node]:
if state[neighbor] == 1:
return True # Cycle found
if state[neighbor] == 0:
if dfs(neighbor):
return True
state[node] = 2 # Done
return False
for node in range(len(graph)):
if state[node] == 0:
if dfs(node):
return True
return False
Cycle Detection Difference
Undirected: check if neighbor ≠ parent. Directed: use three states (unvisited, in-progress, done). A back edge to an in-progress node indicates a cycle.
Problem: Connected Components
def count_components(n, edges):
graph = build_graph(n, edges)
visited = set()
count = 0
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
for node in range(n):
if node not in visited:
dfs(node)
count += 1
return count
Problem: Clone Graph
class Node:
def __init__(self, val=0, neighbors=None):
self.val = val
self.neighbors = neighbors if neighbors else []
def clone_graph(node):
if not node:
return None
clones = {} # original → clone
def dfs(original):
if original in clones:
return clones[original]
clone = Node(original.val)
clones[original] = clone
for neighbor in original.neighbors:
clone.neighbors.append(dfs(neighbor))
return clone
return dfs(node)
Problem: Course Schedule (Topological Sort)
def can_finish(num_courses, prerequisites):
# Build graph: course → prerequisites
graph = [[] for _ in range(num_courses)]
for course, prereq in prerequisites:
graph[course].append(prereq)
# 0: unvisited, 1: in progress, 2: done
state = [0] * num_courses
def dfs(course):
if state[course] == 1:
return False # Cycle
if state[course] == 2:
return True
state[course] = 1
for prereq in graph[course]:
if not dfs(prereq):
return False
state[course] = 2
return True
for course in range(num_courses):
if not dfs(course):
return False
return True
Time and Space Complexity
| Operation | Adjacency List | Adjacency Matrix | |-----------|----------------|------------------| | Space | O(V + E) | O(V²) | | Add edge | O(1) | O(1) | | Check edge | O(degree) | O(1) | | Find neighbors | O(degree) | O(V) | | DFS/BFS | O(V + E) | O(V²) |
Key Takeaways
- Adjacency lists store neighbors in a list per vertex
- More efficient for sparse graphs (most real graphs)
- DFS uses recursion or stack; BFS uses queue
- Cycle detection differs for directed vs undirected graphs
- Most graph algorithms run in O(V + E) with adjacency lists
- Use dictionaries for non-integer vertex labels
Adjacency lists are the standard graph representation for most applications. Understanding how to build them from edge lists and traverse them with DFS/BFS is fundamental to graph algorithms.