A navigation app finds the shortest route from Baku to Shaki in a second, a social network suggests “people you may know”, and a university orders its courses so that nobody takes “Algorithms” before “Programming”. Three different problems, one model: the graph. A graph describes objects (vertices) and the connections between them (edges), and it is one of the most widely used models in computer science.
Graphs and their representation
Graph G = (V, E)Definition
A set V of vertices and a set E of edges (pairs of vertices). Edges may be undirected (friendship) or directed (A → B, “follows”); if each edge has a weight (distance, cost, time), the graph is weighted. A vertex's degree is the number of edges touching it.
Where
- deg(v)
- degree of vertex v
- |V|, |E|
- numbers of vertices and edges
The “handshake lemma”: every undirected edge adds 2 to the degree sum, one at each end. The second inequality is the maximum number of edges in a simple undirected graph.
| Property | Adjacency matrix | Adjacency lists |
|---|---|---|
| memory | O(V²) | O(V + E) |
| is there an edge (u, v)? | O(1) | O(deg u) |
| visit all neighbours of u | O(V) | O(deg u) |
| when to choose it | dense graph (E ≈ V²) | sparse graph (roads, social networks) |
We will use one example graph throughout the lesson. Six vertices A–F and weighted undirected edges: A–B 4, A–C 2, B–C 1, B–D 5, C–D 8, C–E 10, D–E 2, D–F 6, E–F 3. Think of the weights as kilometres.
Breadth-first (BFS) and depth-first (DFS) search
BFS spreads from the start vertex like a wave: first all neighbours, then the neighbours' neighbours. It uses a queue, and in an unweighted graph it yields shortest paths in number of edges. DFS goes as deep as possible along one path and backtracks at dead ends; it works with a stack (or recursion) and is used for connectivity, cycle detection and topological sorting. Both look at every vertex and every edge once: O(V + E).
Example 1: BFS and DFS from F
Problem
Ignoring the weights, run BFS and DFS from F on the example graph. Take neighbours in alphabetical order: A: B, C; B: A, C, D; C: A, B, D, E; D: B, C, E, F; E: C, D, F; F: D, E.
Show solutionHide solution
Solution
Levels: F | D, E | B, C | A.
DFS (recursion): F → D (F's first neighbour) → B (D's first unvisited neighbour) → A → C (A's neighbour) → E (C's unvisited neighbour).
Order: F, D, B, A, C, E — DFS reached A in 4 steps, while BFS found the shortest path (3 edges).
from collections import deque
graph = {'A': ['B', 'C'], 'B': ['A', 'C', 'D'], 'C': ['A', 'B', 'D', 'E'],
'D': ['B', 'C', 'E', 'F'], 'E': ['C', 'D', 'F'], 'F': ['D', 'E']}
def bfs(start):
dist = {start: 0}
queue = deque([start])
while queue:
v = queue.popleft()
for w in graph[v]:
if w not in dist:
dist[w] = dist[v] + 1
queue.append(w)
return dist
def dfs(v, seen):
seen.append(v)
for w in graph[v]:
if w not in seen:
dfs(w, seen)
return seen
print('BFS from F:', bfs('F'))
print('DFS from F:', dfs('F', []))Expected output
BFS from F: {'F': 0, 'D': 1, 'E': 1, 'B': 2, 'C': 2, 'A': 3}
DFS from F: ['F', 'D', 'B', 'A', 'C', 'E']Dijkstra's algorithm: weighted shortest paths
When edges have weights BFS no longer works: three short edges may be cheaper than one long edge. Dijkstra's algorithm (for non-negative weights) repeatedly picks, among the vertices not yet final, the one with the smallest distance (a priority queue), declares it final and updates its neighbours' distances by relaxation.
Where
- dist[v]
- shortest distance from the source to v found so far
- w(u, v)
- weight of the edge u–v (≥ 0)
- T
- running time with a binary heap
| Step: finalised | A | B | C | D | E | F |
|---|---|---|---|---|---|---|
| 0: start | 0 | ∞ | ∞ | ∞ | ∞ | ∞ |
| 1: A (0) | 0 | 4 | 2 | ∞ | ∞ | ∞ |
| 2: C (2) | 0 | 3 | 2 | 10 | 12 | ∞ |
| 3: B (3) | 0 | 3 | 2 | 8 | 12 | ∞ |
| 4: D (8) | 0 | 3 | 2 | 8 | 10 | 14 |
| 5: E (10) | 0 | 3 | 2 | 8 | 10 | 13 |
| 6: F (13) | 0 | 3 | 2 | 8 | 10 | 13 |
Example 2: recovering the path
Problem
Using the table, find the shortest path from A to F and its length.
Show solutionHide solution
Solution
Backwards from the end: F ← E ← D ← B ← C ← A.
Path: A → C → B → D → E → F, length 2 + 1 + 5 + 2 + 3 = 13.
Note: the obvious-looking A → B → D → F is 4 + 5 + 6 = 15.
import heapq
edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8),
('C', 'E', 10), ('D', 'E', 2), ('D', 'F', 6), ('E', 'F', 3)]
adj = {}
for u, v, w in edges:
adj.setdefault(u, []).append((v, w))
adj.setdefault(v, []).append((u, w))
def dijkstra(src):
dist, prev, pq = {src: 0}, {}, [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in adj[u]:
if d + w < dist.get(v, float('inf')):
dist[v], prev[v] = d + w, u
heapq.heappush(pq, (d + w, v))
return dist, prev
dist, prev = dijkstra('A')
path = ['F']
while path[-1] != 'A':
path.append(prev[path[-1]])
print(dict(sorted(dist.items())))
print(' -> '.join(reversed(path)), '=', dist['F'])Expected output
{'A': 0, 'B': 3, 'C': 2, 'D': 8, 'E': 10, 'F': 13}
A -> C -> B -> D -> E -> F = 13heapq plays the priority queue. A vertex may enter the queue several times; the check d > dist[u] skips outdated entries (“lazy deletion”).Topological sorting and minimum spanning trees
Topological sorting orders the vertices of a directed acyclic graph (DAG) so that for every edge u → v, u comes before v: course prerequisites, the build order of program modules, the order in which spreadsheet cells are recalculated. Kahn's algorithm: put vertices with in-degree 0 into a queue, take one out, delete its edges, and enqueue every vertex whose in-degree drops to 0. If fewer than V vertices come out, the graph has a cycle. Time: O(V + E).
from collections import deque
courses = {'Programming': ['DataStructures', 'Databases'], 'Math': ['Algorithms'],
'DataStructures': ['Algorithms'], 'Databases': ['AI'],
'Algorithms': ['AI'], 'AI': []}
def topo_sort(g):
indeg = {v: 0 for v in g}
for v in g:
for w in g[v]:
indeg[w] += 1
queue = deque(v for v in g if indeg[v] == 0)
order = []
while queue:
v = queue.popleft()
order.append(v)
for w in g[v]:
indeg[w] -= 1
if indeg[w] == 0:
queue.append(w)
return order if len(order) == len(g) else None
print(topo_sort(courses))
print(topo_sort({'X': ['Y'], 'Y': ['Z'], 'Z': ['X']}))Expected output
['Programming', 'Math', 'DataStructures', 'Databases', 'Algorithms', 'AI'] None
None — with such prerequisites no course could ever be started.Minimum spanning tree (MST)Definition
A set of edges that connects all vertices of a connected weighted graph, has no cycle and has the smallest possible total weight. It always has exactly V − 1 edges. Uses: connecting villages with the least cable, designing power and water networks, clustering.
Example 3: Kruskal's algorithm
Problem
Find the minimum spanning tree of the example graph with Kruskal's algorithm: take edges in increasing weight and keep those that do not create a cycle.
Show solutionHide solution
Solution
B–C 1 ✓ → {B, C}
A–C 2 ✓ → {A, B, C}
D–E 2 ✓ → {D, E}
E–F 3 ✓ → {D, E, F}
A–B 4 ✗ — A and B are already in the same component (it would close the cycle A–C–B)
B–D 5 ✓ → all vertices joined; 5 = V − 1 edges, stop.
MST: {B–C, A–C, D–E, E–F, B–D}, total weight 1 + 2 + 2 + 3 + 5 = 13.
edges = [('A', 'B', 4), ('A', 'C', 2), ('B', 'C', 1), ('B', 'D', 5), ('C', 'D', 8),
('C', 'E', 10), ('D', 'E', 2), ('D', 'F', 6), ('E', 'F', 3)]
parent = {v: v for v in 'ABCDEF'}
def find(v):
while parent[v] != v:
v = parent[v]
return v
mst = []
for u, v, w in sorted(edges, key=lambda e: e[2]):
ru, rv = find(u), find(v)
if ru != rv:
parent[ru] = rv
mst.append((u, v, w))
print(mst)
print('total weight:', sum(w for _, _, w in mst))Expected output
[('B', 'C', 1), ('A', 'C', 2), ('D', 'E', 2), ('E', 'F', 3), ('B', 'D', 5)]
total weight: 13find returns a component's “leader”, and if two vertices share a leader the edge would close a cycle. Kruskal's time is dominated by sorting: O(E log E). Prim's algorithm instead grows the tree from one vertex (much like Dijkstra, with a priority queue).Remember
- A graph is G = (V, E); use adjacency lists for sparse graphs (O(V + E)) and a matrix for dense ones (O(V²)).
- BFS goes level by level with a queue and gives unweighted shortest paths; DFS dives deep with a stack; both are O(V + E).
- Dijkstra works with non-negative weights, a priority queue and relaxation in O((V + E) log V).
- A topological order exists only in a DAG; Kahn's algorithm also detects cycles.
- An MST has V − 1 edges; Kruskal sorts edges by weight and avoids cycles with union–find.