Menu Close

# Represent Graph Adjacency Matrix using Java …fcukthecode

Storing Graphs (Adjacency Matrix)
Adjacency Matrix (Storing Graphs) …-fcukthecode 👈 👈 😉

To store a graph, two methods are common:
Adjacency Matrix
Adjacency List

PSEUDO-CODE

``````//The pseudo-code to create the matrix:

Procedure AdjacencyMatrix(N):           //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
for j from 1 to N
Take input -> Matrix[i][j]
endfor
endfor

//We can also populate the Matrix using this common way:

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                       // E -> number of edges
for i from 1 to E
input -> n1, n2, cost
Matrix[n1][n2] = cost
Matrix[n2][n1] = cost
endfor

//For directed graphs, we can remove Matrix[n2][n1] = cost line.``````

The drawbacks of using Adjacency Matrix:
Memory is a huge problem. No matter how many edges are there, we will always need N * N sized matrix where N is the number of nodes. If there are 10000 nodes, the matrix size will be 4 * 10000 * 10000 around 381 megabytes.

This is a huge waste of memory if we consider graphs that have a few edges.

Suppose we want to find out to which node we can go from a node u. We’ll need to check the whole row of u, which costs a lot of time. The only benefit is that, we can easily find the connection between u-v nodes, and their cost using Adjacency Matrix.

Java code implemented using above pseudo-code:

```import java.util.Scanner;
public class Represent_Graph_Adjacency_Matrix
{
private final int vertices;
private int[][] adjacency_matrix;
public Represent_Graph_Adjacency_Matrix(int v)
{
vertices = v;
adjacency_matrix = new int[vertices + 1][vertices + 1];
}
public void makeEdge(int to, int from, int edge)
{
try
{
adjacency_matrix[to][from] = edge;
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
}
public int getEdge(int to, int from)
{
try
{
return adjacency_matrix[to][from];
}
catch (ArrayIndexOutOfBoundsException index)
{
System.out.println("The vertices does not exists");
}
return -1;
}
public static void main(String args[])
{
int v, e, count = 1, to = 0, from = 0;
Scanner sc = new Scanner(System.in);
Represent_Graph_Adjacency_Matrix graph;
try
{
System.out.println("Enter the number of vertices: ");
v = sc.nextInt();
System.out.println("Enter the number of edges: ");
e = sc.nextInt();
graph = new Represent_Graph_Adjacency_Matrix(v);
System.out.println("Enter the edges: <to> <from>");
while (count <= e)
{
to = sc.nextInt();
from = sc.nextInt();
graph.makeEdge(to, from, 1);
count++;
}
System.out.println("The adjacency matrix for the given graph is: ");
System.out.print(" ");
for (int i = 1; i <= v; i++)
System.out.print(i + " ");
System.out.println();
for (int i = 1; i <= v; i++)
{
System.out.print(i + " ");
for (int j = 1; j <= v; j++)
System.out.print(graph.getEdge(i, j) + " ");
System.out.println();
}
}
catch (Exception E)
{
System.out.println("Somthing went wrong");
}
sc.close();
}
}
```

INPUT_1:
Enter the number of vertices:  4
Enter the number of edges:  6
Enter the edges: <to> <from>
1  1
3  4
2  3
1  4
2  4
1  2

OUTPUT:
The adjacency matrix for the given graph is:
1  2  3  4
1  1  1  0  1
2  0  0  1  1
3  0  0  0  1
4  0  0  0  0

ILLUSTRATION