Storing Graphs (Adjacency Matrix)
To store a graph, two methods are common:
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
![](http://www.fcukthecode.com/wp-content/uploads/2022/03/Screenshot-from-2022-03-21-16-06-26.png)
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 .