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| ≪ |V|^2\))
- array \(Adj\) is a map of \(|V|\) lists, 1 for each vertex in \(V\)
- for each \(u ∈ V\), list \(Adj[u]\) contains all vertices \(v\), such that there is an edge \((u, v) ∈ 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) ∈ E\) |
| \(O(E)\) | Edge weight lookup time |
Adjacency Matrix
- Assume named vertices \(1, 2, ..., |V|\) \(\rightarrow\) 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) ∈ E\) |
| \(O(1)\) | Edge weight lookup time |