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