# Graph

March 31, 2017
Posted by Pumpkin

Graph is a non linear data structure, it contains a set of points known as nodes (or vertices) and set of links known as edges which connects the vertices. The pictorial representation is shown in the image in the left pane.

Types of Graph:

• Undirected Graph is a graph that is a set of vertices connected by edges, where the edges are bidirectional.
• Directed Graph is a graph that is a set of vertices connected by edges, where the edges have a direction associated with them.

• Weighted Graph is a graph in which each eadge is given a numerical weight.
• Complete Graph is a graph in which every vertex directly connected to every other vertex

Graph Representation:

Adjacency Matrix: Adjacency Matrix is a 2D array of size V x V where V is the number of vertices in a graph. Let the 2D array be adj[][], a slot adj[i][j] = 1 indicates that there is an edge from vertex i to vertex j.

We can also represent weighted graph by putting weight of the edge instead of 1.

In the right pane we have shown the Adjancency Matrix representation of the above graph.

This representation is easy to implement. Removing edges and find checking link between two vertices is done in O(1) time

This way of representation is not effective as when there is very large number of vertices we are not ustilizing the space effectively(Consumes O(V^2)). Even adding new vertex to the matrix is also costly operation.  So we have one more graph representation Adjacency List.

Adjacency List: An array of linked lists is used. Size of the array is equal to number of vertices. Let the array be array[]. An entry array[i] represents the linked list of vertices adjacent to the ith vertex.

Image in the left pane is Adjacency List representation of the Directed Graph shown in the first image.

Here we are able to reduce the space complexity to O(|V|+|E|) which is much lower than previous case. Here adding new vertex to the graph is also easy. But this comes one trade off when we want to check  whether there is an edge from vertex u to vertex v, it is not efficient and can be done O(V). Which was O(1) in case of Adjacency Matrix.

```
public class Graph{

private int v;
/**
*  We initialize the Graph with number of vertices v in the graph
*/
public Graph(int v) {
this.v = v;
for (int i = 0; i < v; i++) {
}
}

/**
* This method will add an  edge between node u and w.
*/
}
}```

The above is the simple implementation of the Adjacency List using array of linked list. The same way we can also implement graph representation using Adjacency Matrix.

References: Wiki Pages

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
```<pre><code class="java">
String foo = "bar";
</code></pre>
```