Graphs and graph search

Graphs model anything made of objects and connections: road networks, computer networks, web pages and links, course prerequisites, social networks and the states of a robot. CMPUT-272 lesson 12 introduced the vocabulary of graphs, degrees, paths and trees. This lesson turns to algorithms. It compares ways of storing a graph in memory and then develops the two fundamental ways of exploring one, breadth-first search and depth-first search. Both run in time linear in the size of the graph, and most of the graph algorithms in lessons 8 to 10 are built on top of them.

Graph vocabulary for algorithms

A graph \(G = (V, E)\) has a set \(V\) of vertices and a set \(E\) of edges. In an undirected graph an edge is an unordered pair \(\{u, v\}\); in a directed graph it is an ordered pair \((u, v)\) from \(u\) to \(v\). A weighted graph assigns each edge a number, such as a length or a cost. We write \(n = |V|\) and \(m = |E|\). An undirected simple graph has at most \(n(n-1)/2\) edges and a directed one at most \(n(n-1)\). A graph is sparse if \(m\) is close to \(n\), as in road networks where each intersection meets a handful of roads, and dense if \(m\) is close to \(n^2\).

Because graph sizes have two parameters, running times are expressed in both: \(\Theta(n + m)\), read linear in the size of the graph, is the best we can hope for when an algorithm must look at every vertex and edge. A path is a sequence of vertices joined by edges; its length is the number of edges, or the sum of weights in a weighted graph. An undirected graph is connected if there is a path between every pair of vertices, and its connected components are its maximal connected pieces.

Representing a graph

There are two standard representations. An adjacency matrix is an \(n \times n\) array whose entry in row \(u\), column \(v\) is 1, or the weight, if there is an edge from \(u\) to \(v\). An adjacency list stores, for each vertex, a list of its neighbours. In Python a dictionary of lists, or a list of lists indexed by vertex number, is natural; in C, the arrays-of-linked-lists or dynamic arrays from CMPUT-201 lesson 9 do the job.

Most real graphs are sparse, and most algorithms in this course spend their time listing neighbours, so adjacency lists are the default. A road network of Canada with a few million intersections would need trillions of matrix cells but only a few million list entries. The matrix wins when the graph is dense or when constant-time edge tests dominate, and it is the natural representation for algorithms built on matrix arithmetic. In an undirected graph each edge appears in two lists, so the lists hold \(2m\) entries; the handshaking lemma from CMPUT-272, \(\sum_v \deg(v) = 2m\), is exactly this count.

Breadth-first search

Breadth-first search, or BFS, explores a graph outward from a source vertex \(s\) in layers. It first visits \(s\), then all vertices one edge away, then all vertices two edges away, and so on. A first-in, first-out queue enforces the order: dequeue a vertex, look at each neighbour, and if the neighbour has not been seen, mark it, record its distance as one more than the current vertex's and its parent as the current vertex, and enqueue it. Each vertex enters the queue at most once and each adjacency list is scanned once, so BFS runs in \(\Theta(n + m)\) time with adjacency lists.

from collections import deque

def bfs(adj, s):
    dist = {s: 0}
    parent = {s: None}
    order = []
    q = deque([s])
    while q:
        u = q.popleft()
        order.append(u)
        for v in adj[u]:
            if v not in dist:              # first time seen: shortest distance found
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent, order

def path(parent, t):
    out = []
    while t is not None:
        out.append(t)
        t = parent[t]
    return out[::-1]

edges = [('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D'), ('C', 'E'), ('D', 'F'), ('E', 'F'), ('F', 'G')]
adj = {}
for u, v in edges:
    adj.setdefault(u, []).append(v)
    adj.setdefault(v, []).append(u)
dist, parent, order = bfs(adj, 'A')
print('visit order:', ' '.join(order))
print('distances  :', dict(sorted(dist.items())))
print('path A to G:', ' -> '.join(path(parent, 'G')))

visit order: A B C D E F G
distances  : {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3, 'G': 4}
path A to G: A -> B -> D -> F -> G

BFS computes shortest paths in unweighted graphs: when a vertex is first discovered, its recorded distance equals the minimum number of edges from \(s\). The proof uses an invariant on the queue: at all times, the distances of the vertices in the queue are non-decreasing from front to back and differ by at most 1. So vertices are dequeued in order of distance, and a vertex at distance \(k+1\) is discovered while processing some neighbour at distance \(k\), never later. The parent pointers form a BFS tree, and following them back from any vertex gives a shortest path.

Testing bipartiteness with BFS

A graph is bipartite if its vertices can be split into two groups with every edge going between the groups, for example jobs and workers, or students and courses. Equivalently, it can be coloured with two colours so that no edge joins two vertices of the same colour. BFS tests this in linear time: colour the source red, colour each newly discovered vertex the opposite colour of its parent, and check every edge. If some edge joins two vertices of the same colour, the graph is not bipartite. In fact, a graph is bipartite exactly when it has no cycle of odd length, and the BFS layers show why: an edge within one layer closes an odd cycle.

from collections import deque

def bipartition(adj):
    side = {}
    for s in adj:                          # handle every component
        if s in side:
            continue
        side[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if v not in side:
                    side[v] = 1 - side[u]
                    q.append(v)
                elif side[v] == side[u]:
                    return None, (u, v)    # conflict: odd cycle
    return side, None

def make(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, []).append(v); adj.setdefault(v, []).append(u)
    return adj

square = make([(1, 2), (2, 3), (3, 4), (4, 1)])
triangle = make([(1, 2), (2, 3), (3, 1)])
for name, g in (('4-cycle', square), ('3-cycle', triangle)):
    c, bad = bipartition(g)
    print(name, 'bipartite' if c else f'not bipartite, conflict on edge {bad}', dict(sorted(c.items())) if c else '')

4-cycle bipartite {1: 0, 2: 1, 3: 0, 4: 1}
3-cycle not bipartite, conflict on edge (2, 3)

Depth-first search

Depth-first search, or DFS, explores as far as possible along each branch before backing up. From the current vertex it moves to an unvisited neighbour and continues from there; when a vertex has no unvisited neighbours, the search returns to the vertex it came from. The natural implementation is recursive, so the call stack remembers the way back. DFS also runs in \(\Theta(n + m)\) time, because each vertex is visited once and each adjacency list is scanned once.

It is useful to record two timestamps for each vertex: the discovery time \(d[v]\), when the search first reaches \(v\), and the finish time \(f[v]\), when the search has explored everything reachable from \(v\) and returns from it. The intervals \([d[v], f[v]]\) are properly nested or disjoint, like parentheses, which is called the parenthesis theorem. Lesson 8 uses finish times to order the vertices of a directed acyclic graph and to find strongly connected components.

import sys
sys.setrecursionlimit(10000)

def dfs_all(adj):
    time = [0]
    d, f, parent = {}, {}, {}
    def visit(u):
        time[0] += 1; d[u] = time[0]
        for v in adj[u]:
            if v not in d:
                parent[v] = u
                visit(v)
        time[0] += 1; f[u] = time[0]
    for u in adj:                          # restart from every undiscovered vertex
        if u not in d:
            parent[u] = None
            visit(u)
    return d, f, parent

adj = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D', 'E'], 'D': ['F'], 'E': ['F'], 'F': [], 'G': ['F']}
d, f, parent = dfs_all(adj)
for v in adj:
    print(f'{v}: discovered {d[v]:>2}, finished {f[v]:>2}, parent {parent[v]}')

A: discovered  1, finished 12, parent None
B: discovered  2, finished  7, parent A
C: discovered  8, finished 11, parent A
D: discovered  3, finished  6, parent B
E: discovered  9, finished 10, parent C
F: discovered  4, finished  5, parent D
G: discovered 13, finished 14, parent None

In the output, the search starts at A, goes deep through B, D and F, backs up, then explores C and E, and finally restarts at G, which nothing else reaches. F finishes first because it has no outgoing edges. Each interval is nested inside its ancestors' intervals: D's interval [3, 6] sits inside B's [2, 7], which sits inside A's [1, 12].

BFS or DFS?

Both searches also solve simpler problems: deciding whether \(t\) is reachable from \(s\), and labelling connected components of an undirected graph by restarting the search from each unvisited vertex. For very deep graphs, a recursive DFS can exceed Python's recursion limit or overflow the C stack from CMPUT-201; an iterative version with an explicit stack avoids that, although recording finish times then needs a little more care.