Chapter 22: Elementary Graph Algorithms

Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest, Clifford Stein. Introduction to Algorithms, Second Edition. The MIT Press, 2001

The basics of encoding and traversing graphs.

22.1 Representation of Graphs

Introduction to Algorithms defines graphs as $G=(V,E), w$, where $|V|$ is the number of vertices in the graph, $|E|$ is the number of edges in the graph, and $w(u,v), \{u, v\} \subseteq E$ is a function that defines the weight of edges.

$O(|V||E|)$ will be written as $O(VE)$.

The source of a graph traversal is often noted as $s$.

A sparse graph is a graph where $|E|$ is much smaller than $|V|$.

Adjacency List:

• An array, $Adj$, of length $|V|$ such that $Adj[u]=[$all vertices adjacent to $u$ in $G]$
• Uses $\Theta(V+E)$ memory.
• Takes $O(V)$ time to check if an edge $(u,v)$ exists.

Adjacency Matrix:

• A matrix $A=(a_{ij})$ of size $|V|$x$|V|$ such that $a_{ij} = \begin{cases} 1 & \text{if } (i,j) \epsilon E\\ 0 & \text{otherwise} \end{cases}$
• Uses $O(V^2)$ memory. For undirected graphs, the adjacency matrix is symmetrical along its diagonal so slightly less than half of it can be ignored without losing information.
• Takes $O(1)$ time to check if an edge $(u,v)$ exists.

22.2 Breadth-First Search

• Uses a queue in the iterative version
• Takes $O(V+E)$ time to run

22.3 Depth-First Search

• Uses a queue in the iterative version
• Takes $O(V+E)$ time to run

22.4 Topological Sort

A DAG is a directed acyclic graph.

A topological sort of a dag $G=(V,E)$ is a linear ordering of all its vertices such that if $G$ contains an edge $(u,v)$, then $u$ appears before $v$ in the ordering.

TOPOLOGICAL-SORT($G$)

1. call DFS($G$) to compute finishing times $f[v]$ for each vertex $v$
2. as each vertex is finished, insert it onto the front of a linked list
3. return the linked list of vertices

22.5 Strongly Connected Components

A strongly connected component of a directed graph $G=(V,E)$ is a maximal set of vertices $C \subseteq V$ such that for every pair of vertices $u$ and $v$ in $C$, we have both $u \leadsto v$ and $v \leadsto u$; that is, vertices $u$ and $v$ are reachable from each other.

STRONGLY-CONNECTED-COMPONENTS($G$)

1. call DFS($G$) to compute finishing times $f[u]$ for each vertex $u$
2. compute $G^T$
3. call DFS($G^T$), but in the main loop of DFS, consider the vertices in order of decreasing $f[u]$ (as computed in line 1)
4. ouput the vertices of each tree in the depth-first forest formed in line 3 as a separate strongly connected component