Implement Graph Adjacency Matrix in Java, easy in 5 minutes

Today, you will study how to implement Graph Adjacency Matrix 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 are studying today.

Implement Graph Adjacency Matrix in Java

Adjacency matrix representation

An adjacency matrix is two-dimension (2D) array of V x V vertices, with dimensions equivalent to the number of vertices in the graph. Each row and column represent a vertex. The elements of the adjacency matrix have values 0 or 1. A value 1 indicates an adjacency between the vertices and a value of 0 otherwise. I suppose that we are working on the graph blow.

Implement Graph Adjacency Matrix in Java

 

The above graph can be represented in an adjacency matrix like this.

Adjacency Matrix

Let’s have a look on this adjacency matrix above, you see 10 and 20 is adjacency but 10 and 30 otherwise.

Pros and Cons

Pros: This representation is easier to implement and efficient to query as well. For example: checking whether there is an edge from a vertex to another vertex is efficient and can be done O(1), removing an edge takes O(1) time.

Cons: However, it requires more space because we must reserve space for every possible link between all vertices(V x V).

Adjacency Matrix implementation

On the internet, most of examples work with a special case which is a  range of continued numbers, from 0 to n. They match completely with the array indexes. But you usually meet that case in the realities, but it is more complex than it. I try to give you a solution to sort it out.

  • Using an array to store vertices then make it sorted
  • Using the binary search algorithm on an array to get an index of corresponded vertex.
  • Create a graph in adjacency matrix

Now let’s implement Graph Adjacency Matrix in Java or you can see the below program.

Here is output of the above program

Implement Graph Adjacency Matrix in Java, adjacency matrix

That’s all about the tutorial Implement Graph Adjacency Matrix in Java.

References

Graph Data Structure in Java
Graph documentation

Please share it if you found this useful
Hide Buttons