Graph Representations and Traversal Setup
Build directed and undirected graphs with adjacency lists, initialise BFS with a deque, and DFS with a stack or recursion, handling visited tracking.
What is a Graph?
A graph is a collection of nodes (vertices) connected by edges. Unlike trees, graphs can have cycles, multiple paths between nodes, and disconnected components. Graphs model real-world systems like social networks, road maps, dependency trees, and web page links. Almost every non-trivial system-design and algorithm interview touches graphs — mastering their representation and traversal is essential.
# Graph terminology:
# - V: set of vertices (nodes)
# - E: set of edges
# - Directed graph: edges have direction (A -> B but not B -> A)
# - Undirected graph: edges are bidirectional
# - Weighted graph: edges have costs/weights
# - Cyclic: contains at least one cycle
# - Acyclic: no cycles (DAG = Directed Acyclic Graph)
# - Connected: every node reachable from every other
# - Disconnected: multiple isolated components
print('Graph: nodes + edges, directed/undirected, weighted/unweighted')Adjacency List Representation
An adjacency list stores each node's list of neighbours. In Python, use a dict mapping each node to a list of adjacent nodes. This is the most common representation in interview problems: O(V + E) space (efficient for sparse graphs), O(degree) to iterate over neighbours, and O(1) average to check adjacency with a hash set variant. Most LeetCode graph problems use this format.
from collections import defaultdict
# Build an undirected graph
def build_undirected(edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # both directions
return graph
edges = [(0,1), (0,2), (1,3), (2,3), (3,4)]
graph = build_undirected(edges)
print(dict(graph))
# {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2,4], 4:[3]}
# Directed graph: only one direction
def build_directed(edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v) # only u -> v
return graphAll lessons in this course
- Graph Representations and Traversal Setup
- BFS: Shortest Path and Level Traversal
- DFS: Connected Components and Flood Fill
- Cycle Detection in Directed and Undirected Graphs