Graph Adjacency List

   Last Updated: 06 October, 2024       🕓  5 Mins

In graph data structure, the process of storing a graph in the memory of a computer is referred to as a graph representation.

A graph in a data structure can be represented in many ways. The two most common and popular ways to represent a graph are:

1. Adjacency Matrix

2. Adjacency List

In this tutorial, we will learn all about how to represent a graph using Adjacency List in details with example in Java.

What is an Adjacency List in a Graph?

Adjacency lists are a powerful and efficient way to represent graphs in data structure, especially when we are dealing with sparse graphs or when the need to add or remove vertices frequently arises.

Adjacency lists are a preferred representation for most real-world graphs, especially sparse graphs, due to their space efficiency, flexibility, and suitability for common graph algorithms.

Adjacency List for Directed graph

To implement an adjacency list for a directed graph, we have taken a directed and unweighted graph G with 4 vertices and 4 edges.

Output

Adjacency List for Undirected graph

Output

Adjacency List for Directed and Weighted graph

Output

Adjacency List for Undirected and Weighted graph

Output

Advantages of Adjacency List:

• In sparse graphs, an adjacency list significantly reduces memory usage. We only store the existing connections, not a potentially large matrix filled with mostly empty spaces.
• Using an adjacency list makes adding and removing vertices easier and more efficient.
• Adjacency lists work well with graph algorithms such as Depth-First Search (DFS), Breadth-First Search (BFS), and Finding Connected Components.
• We can easily store extra edge information (such as weights) in the adjacency list.
• A graph's edges can be easily traversed in an adjacency list.

Disadvantages of Adjacency List:

• Slower Edge Lookups.
• Less Efficient for Dense Graphs.
• Adjacency list implementation and maintenance are slightly more complex than adjacency matrices.
• Determining a vertex's degree necessitates traversing the whole list of its neighbors, which might be slower than just accessing a row or column in an adjacency matrix.