Posted on

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.

1.Adjacency Matrix representation

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.

2.Adjacency List 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.

graph representation
We eliminate redundant information using adjacency list.

So our first task to tackle graph related problems is to construct required adjacency list and we are done with that.Now, moving to the ways of traversing a Graph.

  1. Breadth First Technique (level-ordered)
  2. Depth First Technique

Types of Graph

Get familiar to graph data structure – types, representation , traversal , problems etc.

This article has been contributed by Prashant Singh Thakur

Write a comment