Graph-Powered Machine Learning

appendix D. Representing graphs

There are two standard ways of representing a graph G = (V, E) in a suitable way to be processed: as a collection of adjacency lists or as an adjacency matrix. Each way can be applied to directed, undirected, and unweighted graphs [Cormen et al., 2009].

The adjacency list representation of a graph G = (V, E) consists of an array Adj of lists, one for each vertex in V. For each vertex u in V, the adjacency list Adj[u] contains all the vertices v for which there exists an edge E_uv between u and v in E. In other words, Adj[u] consists of all the vertices adjacent to u in G.

Figure D.1(b) is an adjacency list representation of the undirected graph in figure D.1(a). Vertex 1 has two neighbors, 2 and 5, so Adj[1] is ...