Graphs Are Just Dots and Connections
Strip away the intimidation and a graph is two things: nodes (vertices) and edges (connections between them). A social network, a map of cities, course prerequisites, a maze grid, the internet ā all graphs. Trees are graphs too, just with rules. Once you see a problem as "things connected to other things," half the work is done.
You'll pick one of two representations. An adjacency list maps each node to its neighbors. An adjacency matrix is a 2D grid where matrix[i][j] says whether an edge exists. For almost every interview and real-world problem, use the adjacency list ā it's memory-cheap for sparse graphs (most graphs are sparse) and iterating a node's neighbors is instant.
from collections import defaultdict
graph = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 3), (2, 3)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # drop this line if the graph is directed
Note that one detail: adding both directions makes it undirected. Adding one makes it directed. Getting this wrong is the most common graph bug, so decide up front which one your problem needs.
BFS and DFS: The Only Two Traversals You Need
Every graph algorithm is a remix of two traversals. BFS explores level by level using a queue. DFS goes as deep as possible before backing up, using a stack (or recursion). The single most important habit: keep a visited set. Without it, cycles trap you in an infinite loop.
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return visited
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
for neighbor in graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
return visited
When do you pick which? BFS finds the shortest path in an unweighted graph because it reaches nodes in order of distance. Use it for "fewest steps," "shortest number of moves," "nearest exit." DFS is your tool for exploring structure ā connected components, cycle detection, path existence, backtracking. Both run in O(V + E): you touch every vertex and every edge once. That linear bound is why traversal feels cheap even on big graphs.
Mark a node visited when you enqueue it in BFS, not when you dequeue it. Otherwise the same node gets queued multiple times before you process it, and your "shortest" distances quietly break.
Grids Are Graphs in Disguise
Interview problems love 2D grids: islands, flood fill, shortest path through a maze. Don't build an explicit graph ā the grid is the graph. Each cell is a node, and its neighbors are the cells up, down, left, and right.
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
visited = set()
def dfs(r, c):
if (r < 0 or r >= rows or c < 0 or c >= cols
or grid[r][c] == "0" or (r, c) in visited):
return
visited.add((r, c))
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
dfs(r + dr, c + dc)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1" and (r, c) not in visited:
islands += 1
dfs(r, c)
return islands
The ((1,0),(-1,0),(0,1),(0,-1)) direction tuple is a pattern you'll reuse constantly. Memorize it. For shortest path through a grid, swap DFS for BFS and count levels.
Cycles and Topological Sort
Detecting a cycle depends on direction. In an undirected graph, a cycle exists if BFS or DFS reaches an already-visited node that isn't the one you just came from. In a directed graph, you track nodes currently on the recursion stack ā revisiting one of those means a back edge, which means a cycle.
Cycle detection in directed graphs pairs naturally with topological sort: ordering nodes so every edge points forward. This is exactly how you resolve "what must happen before what" ā build systems, task schedulers, course prerequisites. Kahn's algorithm uses BFS on in-degrees:
from collections import deque, defaultdict
def topo_sort(graph, n):
indegree = [0] * n
for u in graph:
for v in graph[u]:
indegree[v] += 1
queue = deque(i for i in range(n) if indegree[i] == 0)
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return order if len(order) == n else [] # empty means a cycle exists
That last line is the elegant part: if you can't order every node, the graph has a cycle. One algorithm, two answers.
Shortest Paths When Edges Have Weight
BFS gives shortest paths only when every edge counts the same. Add weights ā distances, costs, times ā and you need Dijkstra's algorithm. It's BFS with a priority queue, always expanding the cheapest-so-far node next.
import heapq
def dijkstra(graph, start, n):
dist = [float("inf")] * n
dist[start] = 0
heap = [(0, start)]
while heap:
d, node = heapq.heappop(heap)
if d > dist[node]:
continue
for neighbor, weight in graph[node]:
new_dist = d + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return dist
Dijkstra runs in O((V + E) log V) and assumes non-negative weights. Negative edges break it ā reach for Bellman-Ford there, but that's rare in interviews. The if d > dist[node]: continue guard skips stale heap entries and is the difference between a correct solution and a slow, buggy one.
Graphs stop being scary once you internalize the core loop: pick a representation, traverse with a visited set, and reach for the variant the problem demands ā BFS for fewest steps, DFS for structure, topo sort for ordering, Dijkstra for weighted cost. If you want more reps on the Python patterns underneath all this, /courses/dsa-python and /courses/advanced-python-programming drill them until they're reflex.