Implement Graph Adjacency List in Java, easy in 5 minutes

Today, you will study how to implement Graph Adjacency List in Java. It’s easy for you to understand if you have basic knowledge about Graph data structure, but you don’t, please refer to the post Graph Data Structure in Java. Now, let’s find out what we study today.

Implement Graph Adjacency List in Java

Adjacency List representation

You know, an adjacency list represents a graph as an array of linked list. Each specified index of the array represents a vertex and each element in its linked list represents the other vertices that have an edge with that vertex. Here is a graph and its adjacency list representation is shown below.

Implement Graph Adjacency List in Java,Adjacency List representation

Have a look at that above image. An array of lists is used. Size of the array is equal to the number of vertices. Suppose that the array is array[]. An entry array[i] represents the list of vertices adjacent to the i th vertex. This representation can also be used to represent a weighted graph.

Pros and Cons

This representation is better space efficiency because it only stores the values for the edges, so it saves spaces O(|V|+|E|). But it is comparatively difficult to implement and less efficient to query. For example, a query whether there is an edge from a vertex to another vertex is not efficient and can be done O(V).

Adjacency List impelementation

We can use Java collection to implement graph adjacency list in Java. Here we use a map to store an array of linked list. The map’s keys are equivalent to vertices then each map’s value is used to store a linked list of other adjacency vertices. Actually, I prefer to use a map than an array with indexes because I can implement any type of vertex object like a number, string, object, etc.

Running the above program, you will get the output like below

Implement Graph Adjacency List in Java

That’s all about Implement Graph Adjacency List in Java.

References

Graph Data Structure in Java

Graph documentation

Please share it if you found this useful
Hide Buttons