Graph Adjacency Representation - Java Program

In this post we'll see how to represent a graph using adjacency list and adjacency matrix. Here we'll see representation for the unweighted graph.

Graph is a data structure which is similar to tree and has nodes and edges. Nodes are generally called vertices when it comes to graph.

What is adjacency

The vertices in a graph are said to be adjacent to one another if they are connected directly by a single edge.

The above graph has 5 vertices (A, B, C, D, E) and 5 edges. The circles represent the vertices and the lines connecting them are edges. In the above figure vertex A is adjacent to B and C but A is not adjacent to vertex D.

A binary tree has a fixed structure; each node has a maximum of two children. Graph doesn't have that kind of fixed structure, in a graph each vertex may be connected to an arbitrary number of other vertices. In the above vertex A is connected to B, C and E vertices.

Because of this kind of structure, to represent a graph two methods are generally used-

Adjacency matrix
Adjacency List

Graph representation using adjacency matrix

An adjacency matrix is a 2-D array in which 0 and 1 are used as elements to indicate whether an edge is present between two vertices or not.

An edge between two vertices is marked using 1
If there is no edge between two vertices then 0 is used

If a graph has n vertices, then adjacency matrix also has n rows and n columns (n X n array).

For the above image which represents an undirected graph the adjacency matrix can be visualized as shown below. An undirected graph means that the edges don't have direction and you can traverse both ways. You can go from vertex A to vertex B or from vertex B to vertex A.

Adjacency matrix representation is easy to implement and efficient in terms of accessing any element, but it is less space efficient because you are storing information about all possible edges rather than just actual connections (adjacency list stores only actual connections).

Undirected Graph adjacency matrix Java Program

public class GraphAdjMatrix {
  private int vertices;
  private int[][] adjMatrix;

  GraphAdjMatrix(int vertices){
    this.vertices = vertices;
    // matrix having same row and columns as vertices
    adjMatrix = new int[vertices][vertices];
  }
  
  public void addEdge(int source, int destination) {
    if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
      System.out.println("Invalid edge addition");
      return;
    }
    adjMatrix[source][destination] = 1;
    // For undirected graph reverse setting also required
    adjMatrix[destination][source] = 1;
  }
  
  public void printGraph() {
    for(int i = 0; i < adjMatrix.length; i++) {
      for(int j = 0; j < adjMatrix[0].length; j++) {
        System.out.print(adjMatrix[i][j] + "\t");
      }
      System.out.println();
    }
  }
  
  public static void main(String[] args) {
    GraphAdjMatrix graph = new GraphAdjMatrix(5);
    graph.addEdge(0, 1); //A-B
    graph.addEdge(0, 2); //A-C
    graph.addEdge(0, 4); //A-E
    graph.addEdge(2, 3); //C-D
    graph.addEdge(3, 4); //D-E

    graph.printGraph();

  }
}

Output

Directed Graph adjacency matrix Java Program

In a directed graph you can traverse in only one direction. The allowed direction is shown with an arrow at the end of the edge.

Adjacency matrix for the above directed graph can be visualized as-

Java code for the directed Graph adjacency matrix requires just commenting a single line in the above code for the undirected graph, the reverse link in the matrix.

public void addEdge(int source, int destination) {
  if((source < 0 || source > vertices) || (destination < 0 || destination > vertices)) {
    System.out.println("Invalid edge addition");
    return;
  }
  adjMatrix[source][destination] = 1;
  // For undirected graph reverse setting also required
  //adjMatrix[destination][source] = 1;
}

With that the output is-

Graph representation using adjacency list

Another way to represent a graph is using an adjacency list which is an array of lists or a list of lists. Each vertex in a list shows all the adjacent vertices as another list, linked to this vertex.

Adjacency list for the above undirected graph can be visualized as-

Undirected Graph adjacency list Java Program

In the Java program Map and List collections are used to represent adjacency list. Each map key has an associated list to show the adjacent vertices.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;


public class GraphAdjList {
  int vertices;
  Map<String, List<String>> adjList;
  
  GraphAdjList(int vertices){
    this.vertices = vertices;
    adjList = new HashMap<>();

  }
  
  public void addEdge(String source, String destination) {
    adjList.computeIfAbsent(source, k->new ArrayList<>()).add(destination);
    // For undirected graph
    adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(source);
  }
  
  public void printGraph() {
    for(Map.Entry<String, List<String>> es :adjList.entrySet()) {
      System.out.print("Vertex " + es.getKey() + " connects to: ");
      List<String> list = es.getValue();
      for (String s : list) {
        System.out.print("[" + s + "] ");
      }
      System.out.println();
    }
  }
  public static void main(String[] args) {
    GraphAdjList graph = new GraphAdjList(5);
    graph.addEdge("A", "B");
    graph.addEdge("A", "C");
    graph.addEdge("A", "E");
    graph.addEdge("C", "D");
    graph.addEdge("D", "E");
    
    graph.printGraph();
  }
}

Output

Vertex A connects to: [B] [C] [E] 
Vertex B connects to: [A] 
Vertex C connects to: [A] [D] 
Vertex D connects to: [C] [E] 
Vertex E connects to: [A] [D]

As you can see with adjacency list you store only the actual connections so it is more space efficient.

Directed Graph adjacency list Java Program

In case of directed graph, you can traverse in only one direction.

Adjacency list for the above directed graph can be visualized as-

Java code for the directed Graph adjacency matrix requires just commenting the line that creates a reverse link in the list.

public void addEdge(String source, String destination) {
  adjList.computeIfAbsent(source, k->new ArrayList<>()).add(destination);
  // For undirected graph
  //adjList.computeIfAbsent(destination, k->new ArrayList<>()).add(source);
}

With that change the output is-

Vertex A connects to: [B] [C] [E] 
Vertex C connects to: [D] 
Vertex D connects to: [E]

That's all for this topic Graph Adjacency Representation - Java Program. If you have any doubt or any suggestions to make please drop a comment. Thanks!

>>>Return to Java Programs Page

Related Topics

You may also like-

Tech Tutorials

Friday, October 10, 2025