What a Graph Is
A graph is a generalization of a tree: a set of nodes (also called vertices) connected by edges, where cycles are allowed and there is no required root. Graphs model real-world systems everywhere — road networks, social connections, dependency chains, network topology.
Two key properties to identify upfront in any graph problem:
- Directed vs. Undirected: Can you traverse an edge in both directions?
- Weighted vs. Unweighted: Do edges have costs?
Representing a Graph in Code
Adjacency List (preferred for sparse graphs — most interview problems):
# Build an undirected graph from an edge list
edges = [(0,1), (0,2), (1,3), (2,3)]
graph = {i: [] for i in range(4)}
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # omit this line for directed graphs
# graph = {0:[1,2], 1:[0,3], 2:[0,3], 3:[1,2]}
Adjacency Matrix (preferred for dense graphs or when you need O(1) edge lookup):
n = 4
matrix = [[0]*n for _ in range(n)]
for u, v in edges:
matrix[u][v] = 1
matrix[v][u] = 1 # omit for directed
DFS and BFS on Graphs
The key difference from trees: graphs can have cycles, so you must track visited nodes.
# DFS — iterative with explicit stack
def dfs(graph, start):
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop()
if node in visited:
continue
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return order
# BFS — queue-based
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return order
When to Use DFS vs. BFS on Graphs
| Goal | Use |
|---|---|
| Detect a cycle | DFS (track recursion stack) |
| Find connected components | DFS or BFS |
| Shortest path (unweighted) | BFS (guarantees fewest hops) |
| Topological sort | DFS (postorder) |
| Check if bipartite | BFS (2-color the graph) |
Topological Sort applies to Directed Acyclic Graphs (DAGs) — think task scheduling where some tasks must complete before others. The result is a linear ordering of nodes such that for every directed edge u → v, node u appears before v.
def topological_sort(graph, n):
visited, result = set(), []
def dfs(node):
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs(neighbor)
result.append(node) # postorder: append after all descendants
for node in range(n):
if node not in visited:
dfs(node)
return result[::-1] # reverse postorder = topological order