Adjacency List Visually Explained

Visually Explained Algorithms

The adjacency list is another way to represent adjacent vertices. Why would you want to create an adjacency list? Again, to save time. The adjacency list is much more efficient when trying to figure out the adjacent nodes in a graph. Adjacency list also takes up less space than the adjacency matrix. In the adjacency matrix, each node must contain a value, regardless of whether it contains an edge to another node or not. The adjacency list only contains nodes that are connected. Let’s look at an example of how someone would create an adjacency list from a directed graph.

We’ll start by creating 6 elements in the array to represent the 6 nodes. Each array element will store a linked list.

Going through the graph, vertex 1 is connected to vertex 6. So, we update the adjacency list for vertex 1. The loop at the end indicates that the there are no additional nodes that vertex 1 points to. So, it points to NIL.

Vertex 2 points to two other vertices: vertex 1 and vertex 5. We update the list to have vertex 2 point to 1 and then to 5.

Vertex 3 points to 2 and 5.

Vertex 4 points to vertex 6.

Vertex 5 points to vertices 1, 3, 4, and 6.

Finally, vertex 6 points to vertices 1, 2, and 5.

By observation, we can quickly see that a significant amount of space is saved by switching to an adjacency list from an adjacency matrix. The time complexity stays roughly the same.

If you liked what you read, my book, An Illustrative Introduction to Algorithms, covers this Graph Representation and many more.

 

Leave a Reply