1.
Introduction
2.
Applications of Graphs
3.
Types of Graphs
4.
Implementation of Graph
4.1.
4.2.
5.
5.1.
What is a graph data structure?
5.2.
What is the difference between a graph and a tree?
5.3.
What are some common algorithms for graph traversal?
5.4.
What is the shortest path problem in graph theory?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

# Graph Implementation using STL

Nilesh Kumar
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

## Introduction

A graph is a data structure which is used to implement or store paired objects and their relationships with each other.

It consists of two main components:

• Vertex/Nodes
These are used to represent the objects. E.g. Let us consider a graph of cities where every node is a city. Let A and B be two such cities represented by two nodes A and B.

• Edges
These represent relationships between those objects. E.g. Let the roads connecting these cities be considered as the relationship that they hold with each other i.e. the edge. One more parameter can be considered which is called the weight. If the roads consist of values like the distance then we can say to reach from city A to B we require some D distance, where D becomes the weight of the edge between A and B.

## Applications of Graphs

• Maps
Geographical maps shows various places and routes, routes being the edges of the place nodes. E.g. Google maps

• Social Networks
Let us consider Facebook where every profile is treated as a node and their friendships(relationship) as the edge between two profiles.

• E-Commerce Recommendation System
We all have seen the recommendation system in an e-commerce site like Flipkart, Amazon etc, which uses the same graphs for finding the recommendations for the particular product we have visited recently.
Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

## Types of Graphs

• Undirected Graphs
These types of graphs have bidirectional relationships. E.g. let the two cities be connected by a bidirectional road i.e. we can go from A to B and also from B to A.
• Directed Graphs
These types of graphs have only one-way connectivity. E.g. if A is connected to B does not necessarily mean B is connected to A. Mostly these types are represented with arrowheads. Below we can go from a to b but not from B to A.
• Unweighted Graphs
These types of graphs have edges without any weights i.e. let say there is uniform cost for going from one edge to another.
• Weighted Graphs
These types of graphs have edges with weights i.e. let say there is a cost incurred for going from one edge to another.
• Cyclic Graph
These types of graphs have edges connected in cyclic order. E.g. b-c-d-e contains a cycle.

## Implementation of Graph

Now we can represent graph generally in two ways:

Let us first discus the implementation of Graph using Adjacency Matrix.

In this method, we consider a matrix of vertices which contains the relationship information in the matrix i.e. if a vertex u is connected to vertex v the there will be an edge/relationship at matrix[u][v] and it might be bidirectional or unidirectional weighted or unweighted depending up the need of the problem.

Implementation

``````struct Graph {
int V;
int E;
};
int i,u,v;
Graph *G = new Graph;
// cout<<“Enter no. of Vertices “; cin>>G->V;
//cout<<“Enter no. of Edges “; cin>>G->E;
for(int j = 0;j<G->V;j++)
for(int u = 0 ;u<G->V;u++)
for(int v = 0;v<G->V;v++)

for(int i = 0;i<G->E;i++)
{
//Undirected Graph
//cout<<"Enter edge pair: _%d_%d_ ";
//for directed graph adj(u,v) gives only the edge u->v
cin>>u>>v;
}
return G;
}``````

Here we can also travel the Graph using Breadth First Search(BFS)

``````struct Graph {
int V;
int E;
};
struct Graph createAdjMatrix(int V,int E) { struct Graph G = new Graph;
G->V = V;
G->E = E;
for(int i = 0;iV;i++)
{
for(int j = 0;jV;j++)
}
for(int i = 0;iE;i++)
{
int u,v;
cin>>u>>v;
}
return G;
}
void BFS(struct Graph* G,int u,bool* visited){
queue q;
q.push(u);
visited[u] = true;

while(!q.empty()){
int currentVertex = q.front();
q.pop();
cout<<currentVertex<<" ";

for(int i = 0;i<G->V;i++)
{
if(i==currentVertex)
continue;
{
q.push(i);
visited[i] = true;
}
}
}
}
void BFSutil(struct Graph* G)
{
bool* visited = new bool[G->V];
for(int i = 0;iV;i++)
visited[i] = false;
for(int i = 0;i<G->V;i++)
if(!visited[i])
BFS(G,i,visited);
}``````

Let us see traversal of graph using Depth First Search (DFS Algorithm)

``````struct Graph {
int V;
int E;
list *Adj; // list of vertices
/* Using a List which acts as a Doubly Linked List the input pattern or the order in which input in done effects the DFS traversal. Mostly to achieve a proper DFS traversal using a list we need to take inputs in the Depth First Order */
};
struct Graph *G = new Graph;
cin>>G->V;
cin>>G->E;
for(int i =0;i<G->E;i++)
{
int u,v;
cin>>u>>v;
//Directed Graph
}

return G;
}
void DFSUtil(struct Graph *G,int u,vector& visited){
cout<<u<<” “;
visited[u] = true;
if(!visited[*i])
DFSUtil(G,*i,visited);
}
void DFS(struct Graph* G){
vector visited(G->V,false);
//this will also take care of disconnected graphs
for(int i = 0;iV;i++)
if(!visited[i])
DFSUtil(G,i,visited);
}``````

Space Complexity
Where V is the number of vertices. These are the two ways of traversal in Graph using adjacency matrix. This method is a very space-consuming method for sparse graphs. Hence to reduce the space complexity we use Adjacency List.

Here we take the help of list data structure (STL) in C++, which works on the basis of linked list implementation. Each vertex consists of a list of vertices which are connected to the particular vertex. Let us see the implementation.

Implementation with BFS travel

``````class Graph{
int V;
//array of lists
public:
Graph(int v){
V = v;
}
void addEdge(int u,int v,int bidir = true){
if(bidir)
}
for(int i = 0;i”;
cout< q;
bool *visited = new bool[V]{false};
q.push(src);
visited[src] = true;
int *dist = new int[V]{0};
int *parent = new int[V];
for(int i = 0;i”;
temp = parent[temp];
}
}``````

Implementation of the DFS traversal

``````void dfsUtil(int src,bool* visited){
cout<<src;
visited[src] = true;
if(!visited[nbr])
dfsUtil(nbr,visited);
}
}
void dfs(int src){
bool *visited = new bool[V];
for(int i = 0;i<V;i++)
visited[i] = false;
dfsUtil(src,visited);
}``````

Space Complexity

Where E is the number of edges. Hope this helps aspiring software developers and programmers.

### What is a graph data structure?

A graph is a non-linear data structure consisting of nodes (also known as vertices) and edges. The nodes represent entities, while the edges represent relationships between those entities.

### What is the difference between a graph and a tree?

A tree is a type of graph that is always connected and has no cycles. In other words, a tree is a special case of a graph. Graphs, on the other hand, can have cycles and may not necessarily be connected.

### What are some common algorithms for graph traversal?

There are two main algorithms for graph traversal: depth-first search (DFS) and breadth-first search (BFS). DFS is a recursive algorithm that explores as far as possible along each branch before backtracking, while BFS explores the graph layer by layer, visiting all the neighbors of a node before moving on to the next level.

### What is the shortest path problem in graph theory?

The shortest path problem is the problem of finding the shortest path between two nodes in a graph. The most common algorithm for solving this problem is Dijkstra's algorithm, which uses a priority queue to explore the graph in a greedy manner.

## Conclusion

This article discussed Graph Implementation using STL with all the crucial aspects necessary to implement it. We have also discussed the algorithm in detail and implemented the graph. We also learnt the time and space complexity of the program.

You can also refer

To learn more about DSA, competitive coding, and many more knowledgeable topics, please look into the guided paths on Coding Ninjas Studio. Also, you can enroll in our courses and check out the mock test and problems available to you. Please check out our interview experiences and interview bundle for placement preparations.

Happy Learning!

Live masterclass