Example of Graph Adjacency Matrix in Java
An adjacency matrix is a way of representing a graph as a matrix of 0’s and 1’s or as booleans. It is used to represent the relationship between the vertices or nodes of a graph:
trueindicates that there is an edge between two verticesfalsemeans that there is no edge
The adjacency matrix is a two-dimensional array (2d-array), with rows representing the source vertices and the columns representing the destination vertices.
For example, if matrix[i][j] is true, this indicates that there is an edge from vertex i to vertex j. A value of false indicates that there is no edge between the two vertices i and j.
Suppose we have a graph with 4 vertices A, B, C and D: A is connected to B. B is connected to C. C is connected to D. This graph is One-Directional.
4-Node One-Directional Graph for our Adjacency Matrix
Here’s an example:
public class AdjacencyMatrix {
static int[][] matrix; // Adjacency matrix
static int numVertices; // Number of vertices or nodes
public static void main(String[] args) {
// Set the number of vertices
numVertices = 4;
// Initialize the adjacency matrix
matrix = new int[numVertices][numVertices];
// Add some edges
matrix[0][1] = 1;
matrix[1][2] = 1;
matrix[2][3] = 1;
// Print the adjacency matrix
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
This prints:
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
Here’s a better visualization and explanation (Source code for this at the end).
A B C D
A 0 1 0 0
B 0 0 1 0
C 0 0 0 1
D 0 0 0 0
As we can see, this graph has 4 vertices (A, B, C, and D) and 3 edges: A to B, B to C, and C to D which are represented using adjacency matrix.
Undirected or Bi-Directional edges
In the above example, the adjacency matrix was used to represent a one-directional graph. This means that if there is an edge from vertex i to vertex j, this does not necessarily imply that there is also an edge from vertex j to vertex i. We can also represented undirected edges using adjacency matrices where an edge from i to j is also edge from j to i. In other words, the edge goes both ways.
Adjacency matrices are always symmetrical. If we have an edge from A to B, there must also be an edge from B to A. To represent undirected graphs, we can simply make the adjacency symmetrical.
public class AdjacencyMatrix {
static int[][] matrix; // Adjacency matrix
static int numVertices; // Number of vertices
public static void main(String[] args) {
// Set the number of vertices
numVertices = 4;
// Initialize the adjacency matrix
matrix = new int[numVertices][numVertices];
// Add some edges
matrix[0][1] = 1;
matrix[1][2] = 1;
matrix[2][3] = 1;
// Make the matrix symmetrical
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < i; j++) {
matrix[i][j] = matrix[j][i];
}
}
// Print the adjacency matrix
for (int i = 0; i < numVertices; i++) {
for (int j = 0; j < numVertices; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
Adjacency matrices give us a simple and efficient way of representing graphs, but they can be inefficient in how much space they use up: every node and edge (even if there isn’t an edge) must be explicitly captured. This is inefficient especially for sparse graphs that have low number of edges relative to the number of vertices. In these cases and for large graphs, it may be more efficient to use an adjacency list instead.
Source code for visualizing nodes with labels and edges. This graph has 4 vertices (A, B, C, and D) and 3 edges: A to B, B to C, and C to D.
public class AdjacencyMatrix {
static int[][] matrix; // Adjacency matrix
static int numVertices; // Number of vertices
public static void main(String[] args) {
// Set the number of of vertices or nodes: A, B, C and D
numVertices = 4;
// Initialize the adjacency matrix
matrix = new int[numVertices][numVertices];
// Add some edges
matrix[0][1] = 1;
matrix[1][2] = 1;
matrix[2][3] = 1;
// Print the adjacency matrix
System.out.print(" ");
for (int i = 0; i < numVertices; i++) {
System.out.print((char)('A' + i) + " ");
}
System.out.println();
for (int i = 0; i < numVertices; i++) {
System.out.print((char)('A' + i) + " ");
for (int j = 0; j < numVertices; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}