Graph Theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects.

Introduction To Graph Theory β¦FTCπ π π

To store a graph, two methods are common:

**Adjacency Matrix**- Adjacency List

Adjacency listis a collection of unordered lists used to represent a finite graph.π π πStoring Graphs (Adjacency List)

An **adjacency matrix** is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

Adjacent means ‘next to or adjoining something else’ or to be beside something. For example, your neighbors are adjacent to you. In graph theory, if we can go to node B from node A, we can say that node B is adjacent to node A.

Now we will learn about how to store which nodes are adjacent to which one via Adjacency Matrix. This means, we will represent which nodes share edge between them. Here matrix means 2D array.

Here you can see a table beside the graph, this is our adjacency matrix. Here Matrix[ i ][ j ] = 1 represents there is an edge between i and j. If there’s no edge, we simply put Matrix[ i ][ j ] = 0.

These edges can be weighted, like it can represent the distance between two cities. Then we’ll put the value in Matrix[ i ][ j ] instead of putting 1.

The graph described above is Bidirectional or Undirected, that means, if we can go to node 1 from node 2, we can also go to node 2 from node 1. If the graph was Directed, then there would’ve been arrow sign on one side of the graph. Even then, we could represent it using adjacency matrix.

We represent the nodes that don’t share edge by infinity. One thing to be noticed is that, if the graph is undirected, the matrix becomes symmetric.

The pseudo-code to create the matrix:

```
Procedure AdjacencyMatrix(N): // N-> 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.

Java code implemented using above pseudo-code:

Represent Graph Adjacency Matrix Java π π π

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

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