Graphs are the model behind almost every real-world network: social networks, dependency graphs, road maps, package installers. Master the 6 core graph algorithms and you can solve LeetCode Hard problems, design distributed systems, or implement your own package manager. This 2026 guide covers graph representation, BFS, DFS, topological sort, Dijkstra shortest path, cycle detection, and connected components with Python examples.
Quick 2026 verdict
Represent graphs as adjacency lists (dict of node → neighbors). Use BFS for shortest path in unweighted graphs and level-order traversal. Use DFS for cycle detection, topological sort, and path finding. Use Dijkstra (heap-based) for shortest path in weighted graphs. Learn these 4 patterns in Python and you handle 90 percent of graph interview questions.
Graph representation: adjacency list wins
Three ways to represent a graph. Only one is right for most problems:
- Adjacency list (dict of node → list of neighbors). O(V + E) space. Fast neighbor iteration. Use this by default.
- Adjacency matrix (V × V grid of 0/1). O(V²) space. Slow for sparse graphs. Only use for very dense small graphs or when you need constant-time edge existence checks.
- Edge list (list of (u, v) tuples). O(E) space. Rarely useful except as input format.
from collections import defaultdict
# Adjacency list for graph: A -> B, C
# B -> C, D
# C -> D
# D -> (none)
graph = defaultdict(list)
edges = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "D")]
for u, v in edges:
graph[u].append(v)
# For undirected graph: graph[v].append(u)BFS: breadth-first search (shortest path unweighted)
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
def shortest_path_length(graph, start, target):
if start == target: return 0
visited = {start}
queue = deque([(start, 0)])
while queue:
node, dist = queue.popleft()
for neighbor in graph[node]:
if neighbor == target: return dist + 1
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, dist + 1))
return -1 # unreachableBFS visits nodes in order of distance from the start. That is why it finds shortest paths in unweighted graphs. Time O(V + E), space O(V) for the queue and visited set.
DFS: depth-first search (recursion or explicit stack)
def dfs_recursive(graph, node, visited=None, order=None):
if visited is None: visited = set()
if order is None: order = []
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
dfs_recursive(graph, neighbor, visited, order)
return order
def dfs_iterative(graph, start):
visited = set()
stack = [start]
order = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
order.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
stack.append(neighbor)
return orderDFS is the tool for cycle detection, topological sort, path enumeration (“find all paths from A to B”), and connected component counting. Time O(V + E), space O(V) for the call stack or explicit stack.
Topological sort (dependency ordering)
Given a Directed Acyclic Graph (DAG) where edges represent “A must come before B”, find a valid ordering. Real-world use: task scheduling, course prerequisites, package install order.
def topological_sort(graph, nodes):
in_degree = {node: 0 for node in nodes}
for node in nodes:
for neighbor in graph[node]:
in_degree[neighbor] += 1
queue = deque([n for n in nodes if in_degree[n] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) != len(nodes):
return None # cycle exists, no valid topo order
return orderKahn’s algorithm (above): repeatedly remove nodes with zero incoming edges. If you cannot complete the ordering, the graph has a cycle. Time O(V + E). LeetCode “Course Schedule” and “Course Schedule II” are the canonical problems.
Dijkstra: shortest path in weighted graphs
BFS finds shortest path when all edges have the same weight. When edges have different weights, use Dijkstra (heap-based).
import heapq
def dijkstra(weighted_graph, start):
# weighted_graph: dict of node -> list of (neighbor, weight)
distances = {start: 0}
heap = [(0, start)]
while heap:
dist, node = heapq.heappop(heap)
if dist > distances.get(node, float('inf')):
continue
for neighbor, weight in weighted_graph[node]:
new_dist = dist + weight
if new_dist < distances.get(neighbor, float('inf')):
distances[neighbor] = new_dist
heapq.heappush(heap, (new_dist, neighbor))
return distancesTime O((V + E) log V) with a binary heap. Works only for non-negative edge weights. For negative weights use Bellman-Ford. For all-pairs shortest paths use Floyd-Warshall (O(V³)).
Cycle detection
Undirected graph: during DFS, if you visit a neighbor that is already visited AND is not the immediate parent, you have a cycle.
def has_cycle_undirected(graph, nodes):
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
return False
for node in nodes:
if node not in visited:
if dfs(node, None): return True
return FalseDirected graph: use 3 colors (white/gray/black) or explicit recursion stack tracking to detect back edges.
Connected components (Union-Find is faster)
Counting connected components with BFS/DFS is O(V + E). For dynamic edge-adding, Union-Find (Disjoint Set Union) is faster.
def count_components_bfs(graph, nodes):
visited = set()
count = 0
for node in nodes:
if node not in visited:
count += 1
queue = deque([node])
visited.add(node)
while queue:
curr = queue.popleft()
for neighbor in graph[curr]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return count
class UnionFind:
def __init__(self, nodes):
self.parent = {n: n for n in nodes}
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path compression
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra != rb:
self.parent[ra] = rb
return True
return FalseCommon graph interview patterns
- "Number of islands" (LeetCode 200): DFS or BFS to count connected components in a grid.
- "Clone graph" (LeetCode 133): BFS or DFS while building a hashmap of old_node → new_node.
- "Course schedule" (LeetCode 207): topological sort or cycle detection.
- "Word ladder" (LeetCode 127): BFS on implicit graph (words differing by one letter).
- "Network delay time" (LeetCode 743): Dijkstra's algorithm textbook fit.
Official documentation
Frequently Asked Questions
Should I use adjacency list or adjacency matrix?
Adjacency list for 95 percent of cases: less memory (O(V+E) instead of O(V²)), faster neighbor iteration. Use matrix only when the graph is dense (E close to V²) or when you need constant-time edge lookup. In interviews always start with adjacency list.
BFS or DFS: how do I choose?
BFS when you need shortest path in an unweighted graph OR level-by-level processing. DFS when you need cycle detection, topological order, path enumeration, or connected components. When in doubt, DFS is typically shorter code because recursion is natural.
Can Dijkstra handle negative edges?
No. Dijkstra assumes non-negative edge weights. For negative edges use Bellman-Ford (O(V × E)) which handles negative weights and detects negative cycles. For all-pairs shortest paths with any weights use Floyd-Warshall.
What is the difference between DFS on a tree and DFS on a graph?
Tree DFS never revisits a node because there is only one path to each. Graph DFS must track visited nodes to avoid infinite loops on cycles. Every tree is a graph, but not every graph is a tree.
Do I need to know A* search for interviews?
Rarely. A* is Dijkstra + a heuristic function. It appears in game AI and path-finding but almost never in FAANG interviews. Focus on BFS, DFS, Dijkstra, topological sort, and Union-Find. Master those five and you cover 95 percent of graph interview questions.
How do I represent a graph if node values are strings, not integers?
Adjacency list works identically because Python dict keys can be any hashable type. If your interviewer's boilerplate uses integer node IDs, either use them directly OR maintain two dicts (name -> id, id -> name) and convert at the boundaries.
Related DSA + Interview tutorials
- Big-O Notation Complete Guide for Beginners 2026
- Recursion Explained with Real Examples 2026
- Binary Tree Complete Tutorial with Python 2026
- Dynamic Programming Beginners Guide 2026
Official documentation
- Python.org: heapq module (priority queue for Dijkstra)
- Python.org: collections.deque (queue for BFS)
- Wikipedia: Graph theory foundations
Adrian Mercurio
Full-Stack Developer at PIES IT Solution
Specializes in building complete capstone projects with full documentation. Strong background in PHP/MySQL development and database design. Has personally built and tested over 30 capstone-ready projects with ER diagrams, DFDs, and chapter-by-chapter thesis documentation.
Expertise: PHP · Laravel · Database Design · Capstone Projects · C# · C · C++ · Python · AI Projects · View all posts by Adrian Mercurio →