To store a graph, two methods are common:

Storing Graphs(Adjacency Matrix)

Adjacency Matrix (Storing Graphs) β¦-fcukthecode π π π

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**

**Morae Q!**

- Convert from binary number to decimal number.
- Swap two numbers by using division and multiplication.
- Compute foot and inches into centimetres.
- Concatenate Strings.
- Convert lowercase letters to uppercase letters.
- Compute the sum of all the digits of N.
- Compute the area of the pentagon.
- Get input using scanner.
- Find the distance between two points (x1,y1) and (x2,y2).
- Finding patterns in a file using frep and egrep .
- Detecting a cycle in a directed graph using Depth First Traversal.
- Topological ordering in a Graph.
- Storing graphs using adjacency list.
- Introduction to graph theory.
- Graph Adjacency Matrix pseudo code.
- Adjacency Matrix for storing graphs.
- Dijkstra’s shortest path algorithm .
- Breadth first search (BFS) Algorithm.
- Find the multiple of given number in the list of integers.
- Finding patterns in files using grep .