Graph Algorithms

Summarized notes on Introduction to Algorithms, Chapter 22

---

Representations of Graphs

• two standard ways to represent a graph $G=(V,E)$
  • adjacency list
  • adjacency matrix

Adjacency List

• compact way to represent sparse graphs (when $|E|\ll |V{|}^2$)
• array $Adj$ is a map of $|V|$ lists, 1 for each vertex in $V$
• for each $u\in V$, list $Adj[u]$ contains all vertices $v$, such that there is an edge $(u,v)\in E$
• $Adj[u]$ contains all vertices adjacent to $u$ in $G$

Properties

• if G is directed, sum of lengths of adjacency lists is $|E|$
• if G is undirected, sum of lengths of adjacency lists is $2|E|$
• easy to store attributes, e.g. weight to include multiple attributes
• iterating over all edges is efficient
• issue: checking if $(u,v)$ exists requires searching for $v$ in Adj[u]
• less space efficient for dense graphs
• asymptotically at least equally space-efficient as a matrix
• more complex representation than matrix

Complexity

Bounds
$Ө(V+E)$	Space requirement
$Ө(degree(u))$	Time to list all vertices adjacent to $u$
$O(degree(u))$	Time to determine whether $(u,v)\in E$
$O(E)$	Edge weight lookup time

Adjacency Matrix

• Assume named vertices $1,2,...,|V|$ $\to$ representation is $|V|\cdot |V|$ matrix
• $a_{ij}$ is in matrix if $a_{ij}=1$, and 0 otherwise
• Good for representing dense graphs where $|E|$ close to $|V{|}^2$

Properties

• edge weight maybe stored as value at $m[i][j]$ and store null if edge does not exist
• storing multiple attributes maybe hard; depends on implementation
• easy to check if $(u,v)$ exists
• for undirected graph the matrix is symmetric (graph is its own transpose) → potential to reduce space requirement almost in half based on this symmetry
• require only 1 bit ber entry
• simplest graph representation
• value 1 at center diagonal (top left → bottom right) indicates a cycle in the graph

Complexity

Bounds
$Ө(V^2)$	Space requirement (independent of number of edges)
$O(V^2)$	Iterating all edges
$O(1)$	Time to determine whether $(u,v)\in E$
$O(1)$	Edge weight lookup time