In the last two chapters, we reviewed that Adjacency Matrix and Adjacency List are two ways to represent a graph in a computer program. An adjacency list is the more common representation because it is the more efficient than adjacency matrix. The table below summarizes the performance of the various standard graph data structures. Stars(*) indicate expected amortized time bounds for maintaining dynamic hash tables.

\[\begin{aligned} &\begin{array}{c|c:c:c} & \begin{array}{c} \text { Standard adjacency list } \\ \text { (linked lists) } \end{array} & \begin{array}{c} \text { Fast adjacency list } \\ \text { (hash tables) } \end{array} & \begin{array}{c} \text { Adjacency } \\ \text { matrix } \end{array} \\ \hline \text { Space } & \Theta(V+E) & \Theta(V+E) & \Theta\left(V^{2}\right) \\ \hdashline \text { Test if } u v \in E & O(1+\min \{\operatorname{deg}(u) \text {, deg(v)\})=O(V)} & O(1) & O(1) \\ \text { Test if } u \rightarrow v \in E & O(1+\operatorname{deg}(u))=O(V) & O(1) & O(1) \\ \text { List } v^{\prime} \text { s (out-)neighbors } & \Theta(1+\operatorname{deg}(v))=O(V) & \Theta(1+\operatorname{deg}(v))=O(V) & \Theta(V) \\ \text { List all edges } & \Theta(V+E) & \Theta(V+E) & \Theta\left(V^{2}\right) \\ \text { Insert edge } u v & O(1) & O(1)^{*} & O(1) \\ \text { Delete edge } u v & O(\operatorname{deg}(u)+\operatorname{deg}(v))=O(V) & O(1)^{*} & O(1) \end{array}\\ &\text { Table 1. Times for basic operations on standard graph data structures. } \end{aligned}\]

In light of this comparison, one might reasonably wonder why anyone would ever use an adjacency matrix; after all, adjacency lists with hash tables support the same operations in the same time, using less space. The main reason is that for sufficiently dense graphs, adjacency matrices are simpler and more efficient in practice, because they avoid the overhead of chasing pointers and computing hash functions; they’re just contiguous blocks of memory.

Similarly, why would anyone use linked lists in an adjacency list structure to store neighbors, instead of balanced binary search trees or hash tables? Although the primary reason in practice is almost surely tradition—If they were good enough for Donald Knuth’s code, they should be good enough for yours!—there are more principled arguments. One is that standard adjacency lists are in fact good enough for most applications. Most standard graph algorithms never (or rarely) actually ask whether an arbitrary edge is present or absent, or attempt to insert or delete edges, and so optimizing the data structures to support those operations is unnecessary.

In the rest of this book, unless explicitly stated otherwise, all time bounds for graph algorithms assume that the input graph is represented by a standard adjacency list.

Next we will examine a few of the simplest algorithms for solving problems related to graphs. We start with topological sorting.

---

---