Python Tutorial
Graphs
A set of vertices connected by edges — the model behind maps, social networks, and dependencies.
Vertices and Edges
A graph is a collection of vertices (nodes) joined by edges. Unlike a tree, a graph can have cycles, multiple paths between nodes, and disconnected parts. Edges may be:
- Directed (one-way, like Twitter follows) or undirected (mutual, like Facebook friends).
- Weighted (edges carry a cost/distance) or unweighted.
Two Ways to Represent a Graph
Adjacency list (a dict of neighbors) is compact for sparse graphs. Adjacency matrix (a 2-D grid) gives O(1) edge lookup but uses O(V²) memory.
from collections import defaultdict
# adjacency list for an undirected graph
graph = defaultdict(list)
def add_edge(u, v):
graph[u].append(v)
graph[v].append(u) # omit this line for a directed graph
for u, v in [("A", "B"), ("A", "C"), ("B", "D"), ("C", "D")]:
add_edge(u, v)
print(dict(graph))
# {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}Breadth-First Search (BFS)
BFS explores level by level using a queue. In an unweighted graph it finds the shortest path (fewest edges) from the start.
from collections import deque
def bfs(graph, start):
visited = {start}
order = []
q = deque([start])
while q:
node = q.popleft()
order.append(node)
for nb in graph[node]:
if nb not in visited:
visited.add(nb) # mark on enqueue to avoid duplicates
q.append(nb)
return order
print(bfs(graph, "A")) # ['A', 'B', 'C', 'D']Depth-First Search (DFS)
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=" ")
for nb in graph[start]:
if nb not in visited:
dfs(graph, nb, visited)
dfs(graph, "A") # A B D C (order depends on edge insertion)Always track visited nodes. Without it, cycles cause infinite loops — the key difference from tree traversal.
Weighted Shortest Path: Dijkstra
For weighted graphs with non-negative edges, Dijkstra's algorithm finds the cheapest path using a priority queue.
import heapq
def dijkstra(weighted, start):
dist = {start: 0}
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if d > dist.get(node, float("inf")):
continue
for nb, w in weighted[node]:
nd = d + w
if nd < dist.get(nb, float("inf")):
dist[nb] = nd
heapq.heappush(pq, (nd, nb))
return dist
wg = {"A": [("B", 1), ("C", 4)], "B": [("C", 2)], "C": []}
print(dijkstra(wg, "A")) # {'A': 0, 'B': 1, 'C': 3}Where Graphs Appear
- Maps and GPS routing (weighted shortest path).
- Social networks, recommendation systems.
- Dependency resolution and build order (topological sort on a DAG).
- Web crawling and network analysis.
Best Practices
- Use adjacency lists for sparse graphs, matrices for dense ones.
- BFS for shortest path in unweighted graphs; Dijkstra for weighted (non-negative).
- Always mark visited nodes to handle cycles.
- For real projects use the
networkxlibrary instead of reimplementing algorithms.
Try It Yourself
Exercise 1: For an unweighted graph, which traversal finds the shortest path (fewest edges)?
Show solution
Breadth-first search (BFS) — it explores nodes in order of distance from the start.
Exercise 2: Why must graph traversals track visited nodes when tree traversals do not?
Show solution
Graphs can contain cycles; without a visited set, traversal would loop forever. Trees are acyclic, so no such tracking is needed.
📘 Real-World Deep Dive
Knowing <strong>DSA Graphs (algorithms & data structures)</strong> well is what turns algorithms & data structures from a curiosity into a daily tool — you'll reach for it in nearly every real project.
Real-Life Scenario
An end-to-end usage of DSA Graphs that you'd actually see in a data pipeline or analytics notebook.
Real-Life Example
from collections import defaultdict, deque
def bfs(adj, src):
seen, q = {src}, deque([src])
order = []
while q:
u = q.popleft(); order.append(u)
for v in adj[u]:
if v not in seen:
seen.add(v); q.append(v)
return order
adj = defaultdict(list)
for u, v in [("a","b"),("a","c"),("b","d"),("c","e"),("d","e")]:
adj[u].append(v)
print(bfs(adj, "a"))Expected Output
(see source)Common mistakes
- Off-by-one errors in binary-search: the standard idiom is
while lo <= hiwithmid = (lo + hi) // 2. - Recursive algorithms blow the stack for n > ~10⁴; convert to iterative with an explicit stack.
- Comparison algorithms (
sorted(iterable)) are stable by default in Python — surprising for Java/C++ users. - Treating DSA Graphs as a black box without reading the docs — the API has subtle defaults that bite when you scale.
🚀 Performance & Best Practices
- Use
bisect.bisect_left/bisect_rightinstead of writing your own binary search. - Convert a sorted search into a tuple-access pattern with
numpy.searchsortedfor huge arrays. - Use
heapqfor priority queues instead of maintaining a sorted list manually. - When working with algorithms & data structures, prefer vectorised / batched operations over Python loops.
🧪 Try It Yourself
- Reproduce the snippet on a representative slice of your own data.
- Profile the snippet with
cProfileortimeitand find the single biggest improvement. - Generalise the snippet into a small, reusable function you can drop into future projects.