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]
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.
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.
- Breadth First Technique (level-ordered)
- Depth First Technique
Types of Graph
This article has been contributed by Prashant Singh Thakur