# Graphs representation

Before understanding graph representation in computer languages, let’s understand what is a graph? A graph is collection of edges E : {e1,e2,33…..en} and vertices V : {v1,v2,v3…vn}.
Mathematically, graph is represented as `G = (V,E)`. An edge is pair of vertices (vi, vj) where `i,j<=n` and vertices are the nodes at the two ends of edges.

Below is an example of a graph, where vertices are (1,2,3,4,5,6) and edges are [ (1,2), (1,4), (2,3), (3,5), (5,4), (4,6) ]

There are two types of graphs in general: directed and undirected. The graph you saw in the above example is a directed graph.
A directed graph is where an edge is one way from one vertex to another, whereas the undirected graph has two-way edges, that is, there is no arrowhead at the end of the edge. In representations, if there is an edge from vertex x to vertex y, in an undirected graph, there will be an edge from vertex y to vertex x.

## Graphs representations

There are two ways to represent graphs in programming constructs: adjacency matrix representation and adjacency list representation. Based on the need of algorithm and problem at hand, we decide which way to represent a graph. There are three criteria, which are used to evaluate any representation of a graph.

• How much space a particular representation will take?
• How much time it will take to find if a given edge exists in the graph?
• How long will it take to find all the neighbors of a particular node?
• ### Adjacency matrix representation of a graph

In this representation, we use two dimensional array or matrix G. `G(i,j)` is set to true if there is an edge between vertex i and vertex j.

The advantage of the adjacency matrix representation of a graph is that it is very simple to implement. However, when the number of edges between vertices is sparse, a lot of cells in array or matrix remain empty.

The complexity of graph algorithms is measured in terms of E and V where E is the number of edges and V is the number of vertices.
In adjacency matrix representation, memory used to represent graph is `O(v2)`. If the graph is undirected then when there is an edge between `(u,v)`, there is also an edge between `(v,u)`. So transpose of the adjacency matrix is the same as the original. So we can save half the space when representing an undirected graph using adjacency matrix. Moreover, if there are no weighted edges in the graph, instead of using one byte, we can use one bit to indicate an edge.
To determine if a given edge (u,v) is present, we have to look at G[u][v], if it is true, then there is an edge else not. Time complexity is `O(1)`. To find all the neighbors of a node, we have to scan the entire row, which leads to complexity of `O(n)`.

Adjacency matrix representation of the graph shown above will be:

#### Adjacency matrix implementation of graph

```package com.company.Graphs;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyMatrix {
private boolean [][] G;
private boolean isDirected;

public AdjacencyMatrix(int numNodes, boolean isDirected){
this.G  = new boolean[numNodes+1][numNodes+1];
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){
this.G[start][dest] = true;
if(!isDirected){
this.G[dest][start] = true;
}
}

public boolean isEdge(int start, int dest){
return this.G[start][dest];
}
}

```

Tests

```package test.Graphs;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyMatrixTest {
@Test
public void createGraphTest() {

assertEquals(true, tester.isEdge(3,4));
assertEquals(false, tester.isEdge(1,4));

}
}

```

### Adjacency list representation of graph

In adjacency list representation, we have a table of all vertices of the graph. Each entry in that table will have the list of neighbors which this vertex is connected to.
Space required for adjacency list representation of the graph is `O(V +E)`.
To find if there is an edge (u,v), we have to scan through the whole list at node(u) and see if there is a node(v) in it. In the worst case, it will take `O(E)` time, where E is the maximum number of edges in the graph.
To find all the neighbors of a node, it is just returning all the nodes in the list, which is again of `O(E)` time complexity.

Adjacency list representation can be easily extended to represent graphs with weighted edges. Each node contains another parameter weight. For the edge, `(u,v)`  node in adjacency list of u will have the weight of the edge.

Above graph can be represented in adjacency list as

#### Adjacency list implementation

```package com.company.Graphs;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyList {
private Map<Integer, ArrayList<Integer>> G;
boolean isDirected;

this.G = new HashMap<>();
this.isDirected = isDirected;
}

public void addEdge(int start, int dest){

if(this.G.containsKey(start)){
}else{
this.G.put(start, new ArrayList<>(Arrays.asList(dest)));
}

//In case graph is undirected
if(!this.isDirected) {
if (this.G.containsKey(dest)) {
} else {
this.G.put(dest, new ArrayList<>(Arrays.asList(start)));
}
}
}

public boolean isEdge(int start, int dest){
if(this.G.containsKey(start)){
return this.G.get(start).contains(dest);
}

return false;
}
}

```

Tests

```package test.Graphs;

import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.assertEquals;

/**
* Created by sangar on 21.12.18.
*/
public class AdjacencyListTest {
@Test
public void createGraphTest() {