## Graph Representation and Types

GRAPH REPRESENTATION

By the definition of graph we can conclude that we need two sets to maintain- one for vertices and the other for its edges .Trees are also a special kind of graph.(A subset)

Mathematically we define Graph as an ordered pair of set of edges and vertices, G=(V,E)

Let’s not get confused by the mathematical jargons.We can represent and process graphs using the same old data structures and techniques like arrays,list etc.

Declare a V*V 2D matix and the vertices between which edges exist suppose (i,j) fill 1 else 0 for non-connected vertices: int adj[V][V] Consider any two pairs say vertex (2,4) as they are connected we place a 1 in A[2,4].

This representation is simple yet is not efficient in space as well as time when it comes to processing graph data structure.So, lets look at another better representation.

In this representation we maintain an array of vectors ,so that we can eliminate redundant information of non-connected nodes.Only the connected vertices are stored : vector<int> adj[V]

Try constructing adjacency list using a vector of pairs of two connected vertices.Get comfortable with adjacency list representation before proceeding any further.