Graphs and graph algorithms

Learn how graphs are represented, breadth-first (BFS) and depth-first (DFS) search, Dijkstra's algorithm, topological sorting and minimum spanning trees (Kruskal), step by step.

  • University
  • 25 min
  • 10 questions
  • Lesson 50 of 59

In this lesson you will learn

  • Represent a graph with an adjacency matrix or adjacency lists and justify the choice
  • Trace BFS, DFS and Dijkstra's algorithm by hand
  • Find a topological order and a minimum spanning tree

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.

∑ deg(v) = 2|E||E| ≤ |V| · (|V| − 1) / 2∑ deg(v) = 2|E||E| ≤ |V| · (|V| − 1) / 2

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.

PropertyAdjacency matrixAdjacency lists
memoryO(V²)O(V + E)
is there an edge (u, v)?O(1)O(deg u)
visit all neighbours of uO(V)O(deg u)
when to choose itdense 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.

Sign up free to keep reading

The rest of the lesson, the quiz and your notes open with an Educora account. Signing up takes a minute, and your progress is saved on all your devices.

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

BFS (queue): [F] → take F, add D and E (distance 1) → take D, add B and C (distance 2) → E has no new neighbours → take B, add A (distance 3).
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).
Python
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']
Adjacency lists are stored in a dictionary. BFS returns the distances in the order it discovered the vertices; the DFS order matches our hand trace.

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.

dist[v] ← min(dist[v], dist[u] + w(u, v))T = O((V + E) · log V)

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: finalisedABCDEF
0: start0∞∞∞∞∞
1: A (0)042∞∞∞
2: C (2)0321012∞
3: B (3)032812∞
4: D (8)03281014
5: E (10)03281013
6: F (13)03281013
Dijkstra trace from A (dist values after each step). In step 2 B drops from 4 to 3 (A → C → B); in steps 4 and 5 E and F improve.

Example 2: recovering the path

Problem

Using the table, find the shortest path from A to F and its length.

Show solutionHide solution

Solution

Each update remembers “where we came from” (prev): F was last updated from E (10 + 3), E from D (8 + 2), D from B (3 + 5), B from C (2 + 1), and C from A (0 + 2).
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.
Python
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 = 13
heapq 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).

Python
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
The course graph gets a valid order; the graph with the cycle X → Y → Z → X returns 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

Order: B–C 1, A–C 2, D–E 2, E–F 3, A–B 4, B–D 5, D–F 6, C–D 8, C–E 10.
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.
Python
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: 13
The question “does it make a cycle?” is answered by a union–find structure: find 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.
Spotted a mistake or something inaccurate in this lesson?

Check yourself

10 questions. Every correct answer earns XP.

Question 1 / 10

Question 1 / 10. A road network has V = 10⁴ junctions and E = 3 · 10⁴ roads. How many cells does an adjacency matrix need?