Print Adjacency List for a Directed Graph in Java

An adjacency list is a fundamental representation of a graph in graph theory. Every vertex in a directed graph keeps track of the other vertices to which it has outgoing edges. Particularly for sparse graphs, this form is economical in terms of both space and temporal complexity. This article explains how to create and display a directed graph's adjacency list in Java.

Adjacency List Representation

An adjacency list for a directed graph is a collection of lists or arrays. Each index in this collection represents a vertex, and each list at that index contains the vertices that can be reached directly from the vertex. For instance, if vertex 'v' has edges to vertices 'w' and 'x', the adjacency list for 'v' will include 'w' and 'x'.

Steps to Implement Adjacency List for a Directed Graph

1. Choosing Data Structures

We will use a HashMap to store the adjacency list where:

• The keys represent the vertices.
• The values are lists (or another suitable data structure) containing the vertices to which there are directed edges from the key vertex.

To represent the list of edges from a vertex, we will use an ArrayList, which will allow efficient addition of edges.

2. Class Design

We will define a class Graph to represent the directed graph. The class will contain methods to:

• Add a vertex to the graph.
• Add an edge from one vertex to another.
• Print the adjacency list representation.

3. Adding Vertices and Edges

When adding a vertex, we will initialize an empty list of edges in the adjacency list. When adding an edge, we will append the destination vertex to the list associated with the source vertex.

4. Printing the Adjacency List

The adjacency list will be printed by iterating through the map and displaying each vertex followed by its list of connected vertices.

Let's implement the above steps in a Java program.

File Name: Graph.java

Output:

 Vertex 1: 2 3 Vertex 2: 3 Vertex 3: 4 Vertex 4: 1 

Explanation

An adjacency list is a simple way to represent a directed graph where every element then contains a list of elements connected to it by directed edges. To represent the above mentioned Java graph data structures, we can use a HashMap where the keys of the map hold each vertex of the graph and the value of the map hold at each key, a list or an array of the vertices which the key vertex points to.

To this end, we design a Graph class that enables the addition of vertices, the addition of directed edges, and the printing of the adjacency list. The adjacency list is stored using hashmap, wherein the actual key is a value of an ArrayList of neighbors and this is efficient for storing sparse graph.

It further involves creating available vertices along with edges after that traversing the map to print the adjacency list. Vertex insertion, edge insertion, and edge deletion alike operate in constant time, that is, O(1) while list printing takes O(V + E), where V is the number of vertices and E is the number of edges.

Complexity Analysis

Time Complexity

To add a vertex the time complexity is O(1) because it only involves insertion in the HashMap. To add an edge take O(1) on average adding an element to an ArrayList is done in constant time.

Printing takes O(V + E) time to print list. Whenever vertices are being printed the process will take V while printing edges takes E since we will go through all edges.

Space Complexity

The space complexity is O(V + E ) since we are storing each vertex and the list of the edges which are connected with it.

Conclusion

An adjacency list is good for representing a graph, particularly sparse, as an example above has illustrated. In this article, we have learn to construct a directed graph using an adjacency list in java language. We told you how to add vertices and edges and how to print the adjacency list. This structure is useful in any nodes traversal based algorithms for graphs such as depth first search (DFS) or the bread first search (BFS).