## Graphs

**G = (V,E)**An edge is pair of vertices

**(vi, vj) where i,j <= n**

There are many applications of graph in computer science, like representing connection of roads, flight paths, internet etc.

**Undirected and directed graphs**

Graphs can be undirected or directed. A directed graph is where edge is one way from one vertex to another. While undirected graph has two way edges, that is, there is no arrow head at the end of edge.

**Number of edges**

A directed graph can have at most N^2 edges, one of each pair, while undirected graph will have C(n+1,2) edges. Sparse graph is a graph where number of edges is less than above given number.

**Paths**

Paths in a graph is a sequence of vertices {v1,v2….Vk} such that there exists an edge between consecutive vertices. Formally, we can say that v1,v2,…vk is a path if (vi, vi+1) belongs to edges.

**In-degree and out-degree**

In-degree is number of edges which are ending on a given vertex. Out-degree is number of edges going out of given vertex.

Let’s see how above terminology applies for below graph.

Graph |

**Vertex list v = {1,2,3,4,5,6}****Edge list e = {(2,1)(2,6)(1,4)(4,3)(3,5)(3,6)(5,6)}****Path p = {1,4,3,5,6}****In degree of 3 is 1, out degree of 3 is 2**

**Graphs representations**

**1. Adjacency matrix**

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

Advantage of this representation is that is very simple to implement. However, when number of edges between vertices are sparse, lot of cells remain vacant.

Complexity of graph algorithms is measured in terms of E and V where E is number of edges and V is number of vertices.

In this representation memory used to represent graph is O(V^2). If graph is undirected then when there is an edge between (u,v), there is also an edge between (v,u). So transpose of adjacency matrix is same as original. So we can save half the space in case we are representing an undirected graph using adjacency matrix. Moreover, if there are no weighted edges in graph, instead of using one byte, we can use one bit to indicate edge.

Above graph can be represented as

Adjacency matrix represnetation |

**Code****2. Adjacency list**

In this representation, we have a table of all vertices of graph. Each entry in that table will have list of vertices which it is connected to. It is useful where graph is sparse.

Memory required for this representation of graph is O(V +E ).

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

Above graph can be represented in adjacency list as

Adjacency list representation of graph |

**Code**