Graph Implementation using STL

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:

• 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;
}

You can also try this code with Online C++ Compiler

Run Code

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);
}

You can also try this code with Online C++ Compiler

Run Code

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);
}

You can also try this code with Online C++ Compiler

Run Code

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];
}
}

You can also try this code with Online C++ Compiler

Run Code

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);
}

You can also try this code with Online C++ Compiler

Run Code

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

• Introduction to C++
   
• Data Structure
   
• Detect cycle in an undirected graph
   
• Application of graph data structure
   
• Application of Linked List

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!