Representing Graphs with Adjacency List

One of the most common and efficient ways to represent graphs is through an adjacency list.

What is an Adjacency List?

An adjacency list is a way to represent graph data structures where each vertex (or node) stores a list of vertices it is connected to. It's often implemented as a dictionary or a Map in JavaScript, where each key represents a vertex, and its value is an array of connected vertices. Thinking back to the concept of neighbors, we'll store each node's outgoing neighbors in its value array.

Why use an Adjacency List?

• Efficient Storage: Adjacency lists are particularly efficient for storing sparse graphs, where most vertices have relatively few connections. This means you only need to store the connections that actually exist, saving memory compared to methods that track all possible connections, even those that aren't present.
• Quick Lookups: You can easily find all connections of a specific vertex by accessing its key.
• Easy Implementation: Adjacency lists are relatively straightforward to code up.

Adjacency List in JavaScript

We can use a Map or an object to create our adjacency list in JavaScript. Just note that if we decide to use an object, the keys would have to be strings. Since we are working with integers, a Map is a better choice.

const adjList = new Map();
adjList.set(1, [2, 3]);
adjList.set(2, [4]);
adjList.set(3, [5]);
adjList.set(4, []);
adjList.set(5, [6]);
adjList.set(6, []);

Note that graphs can also be represented as an adjacency matrix, which is beyond the scope of this book.