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.
The above graph can be represented in an adjacency matrix like this.
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.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 |
// Simple program implements a Graph in adjacency matrix import java.util.*; class Graph { private int size; private boolean adjMatrix[][]; Graph(Integer s){ this.size = s; adjMatrix = new boolean[size][size]; } // adds a new edge to the graph public void addEdge(Integer i, Integer j) { adjMatrix[i][j] = true; adjMatrix[j][i] = true; } // remove a edge to the graph public void removeEdge(Integer i, Integer j) { adjMatrix[i][j] = false; adjMatrix[j][i] = false; } // display edges of a vertex with other. public void displayEdgesOfVertex(Integer[] vertices,Integer index){ for (int i=0; i<adjMatrix.length; i++) { if (adjMatrix[index][i]) { System.out.println(vertices[index] + " is connected to " + vertices[i]); } } } // get graph size public Integer size() { return this.size; } public boolean existEdge(Integer i, Integer j) { return adjMatrix[i][j]; } // Displays the adjancency matrix of graph. public String toString() { StringBuilder s = new StringBuilder(); for (int i = 0; i < size; i++) { s.append(i + ": "); for (boolean j : adjMatrix[i]) { s.append((j?1:0) + " "); } s.append("\n"); } return s.toString(); } } // Main class public class Main { public static void main(String args[]) { // create new graph instance Graph g = new Graph(4); // the create an array of vertices Integer[] vertices = new Integer[g.size()]; vertices[0] = 20; vertices[1] = 30; vertices[2] = 10; vertices[3] = 40; // sort vertices array // then use binary search algorthim to get the index of vertices Arrays.sort(vertices); int index20 = Arrays.binarySearch(vertices,20); int index10 = Arrays.binarySearch(vertices,10); int index30 = Arrays.binarySearch(vertices,30); int index40 = Arrays.binarySearch(vertices,40); //System.out.println(index); // edges are added. g.addEdge(index10, index20); g.addEdge(index10, index40); g.addEdge(index20, index10); g.addEdge(index20, index30); g.addEdge(index30, index20); g.addEdge(index30, index40); g.addEdge(index40, index10); g.addEdge(index40, index30); // print the graph. System.out.println("Here is the graph:\n" + g.toString()); // print number of vertices in the graph. System.out.println("Number of vertices graph: "+g.size()); //check a edges exists or not System.out.print("Vertex 40 and 20 exists an edges? "); System.out.println(g.existEdge(index40,index20)?"YES":"NO"); // print number of edges of a vertex. System.out.println("Number of edges of vertex 40:"); g.displayEdgesOfVertex(vertices,index40); } } |
Here is output of the above program
That’s all about the tutorial Implement Graph Adjacency Matrix in Java.
