Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Last Updated: Mar 27, 2024
Difficulty: Medium

Graph Implementation using STL

Leveraging ChatGPT - GenAI as a Microsoft Data Expert
Speaker
Prerita Agarwal
Data Specialist @
23 Jul, 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. 

Graph Implementation using STL

 

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.
Undirected graph
  • 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.
Directed Graphs
  • 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.
Unweighted Graphs
  • 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.
Weighted Graphs
  • Cyclic Graph
    These types of graphs have edges connected in cyclic order. E.g. b-c-d-e contains a cycle.
Cyclic Graph

Implementation of Graph

Now we can represent graph generally in two ways:

  • Adjacency Matrix
     
  • Adjacency List
     

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

Adjacency Matrix Implementation

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** Adj;
};
struct Graph *adjMatrixOfGraph(){
int i,u,v;
Graph *G = new Graph;
// cout<<“Enter no. of Vertices “; cin>>G->V;
//cout<<“Enter no. of Edges “; cin>>G->E;
G->Adj = new int*[G->V];
for(int j = 0;j<G->V;j++)
     G->Adj[j] = new int[G->V];
for(int u = 0 ;u<G->V;u++)
    for(int v = 0;v<G->V;v++)
        G->Adj[u][v] = 0;

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;
        G->Adj[u][v] = 1;
        G->Adj[u][v] = 1;
}
return G;
}

 

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

struct Graph {
int V;
int E;
int** Adj;
};
struct Graph createAdjMatrix(int V,int E) { struct Graph G = new Graph;
G->V = V;
G->E = E;
G->Adj = new int*[G->V];
for(int i = 0;iV;i++)
{
G->Adj[i] = new int[G->V];
for(int j = 0;jV;j++)
G->Adj[i][j] = 0;
}
for(int i = 0;iE;i++)
{
int u,v;
cin>>u>>v;
   G->Adj[u][v] = 1;
    G->Adj[v][u] = 1;
}
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;
        if(!visited[i] && G->Adj[currentVertex][i])
        {
            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 *createAdjList(){
struct Graph *G = new Graph;
cin>>G->V;
G->Adj = new list[G->V];
cin>>G->E;
for(int i =0;i<G->E;i++)
{
    int u,v;
    cin>>u>>v;
    //Directed Graph
    G->Adj[u].push_back(v);
    //G->Adj[v].push_back(u);
}

return G;
}
void DFSUtil(struct Graph *G,int u,vector& visited){
cout<<u<<” “;
visited[u] = true;
for(auto i = G->Adj[u].begin();i!=G->Adj[u].end();i++)
    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.

Adjacency List Implementation

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
list *adjList;
public:
Graph(int v){
V = v;
adjList = new list[V];
}
void addEdge(int u,int v,int bidir = true){
adjList[u].push_back(v);
if(bidir)
adjList[v].push_back(u);
}
void printAdjList(){
for(int i = 0;i”;
for(auto element : adjList[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;
for(auto nbr : adj[src]){
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.

Must Read Difference between ArrayList and LinkedList

Frequently Asked Questions

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!

Topics covered
1.
Introduction
2.
Applications of Graphs
3.
Types of Graphs
4.
Implementation of Graph
4.1.
Adjacency Matrix Implementation
4.2.
Adjacency List Implementation
5.
Frequently Asked Questions
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