Graph data structure
Graph Implementation in C++ using STL
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges)
{
// insert at the end
adjList[edge.src].push_back(edge.dest);
// uncomment the following code for undirected graph
// adjList[edge.dest].push_back(edge.src);
}
}
};
// Function to print adjacency list representation of a graph
void printGraph(Graph const &graph, int N)
{
for (int i = 0; i < N; i++)
{
// print the current vertex number
cout << i << " ——> ";
// print all neighboring vertices of a vertex `i`
for (int v: graph.adjList[i]) {
cout << v << " ";
}
cout << endl;
}
}
// Graph Implementation using STL
int main()
{
// vector of graph edges as per the above diagram.
// Please note that the initialization vector in the below format will
// work fine in C++11, C++14, C++17 but will fail in C++98.
vector<Edge> edges =
{
{ 0, 1}, { 1, 2 }, { 2, 0 }, { 2, 1 },
{ 3, 2 }, { 4, 5 }, { 5, 4 }
};
// total number of nodes in the graph
int N = 6;
// construct graph
Graph graph(edges, N);
// print adjacency list representation of a graph
printGraph(graph, N);
return 0;
}
Output:
(0, 1, 6)
(1, 2, 7)
(2, 0, 5) (2, 1, 4)
(3, 2, 10)
(4, 5, 3)
(5, 4, 1)
Breadth-First Search (BFS) – Iterative and Recursive Implementation
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Perform BFS recursively on the graph
void recursiveBFS(Graph const &graph, queue<int> &q,
vector<bool> &discovered)
{
if (q.empty()) {
return;
}
// dequeue front node and print it
int v = q.front();
q.pop();
cout << v << " ";
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
if (!discovered[u])
{
// mark it as discovered and enqueue it
discovered[u] = true;
q.push(u);
}
}
recursiveBFS(graph, q, discovered);
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {5, 9},
{5, 10}, {4, 7}, {4, 8}, {7, 11}, {7, 12}
// vertex 0, 13, and 14 are single nodes
};
// total number of nodes in the graph
int N = 15;
// build a graph from the given edges
Graph graph(edges, N);
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N, false);
// create a queue for doing BFS
queue<int> q;
// Perform BFS traversal from all undiscovered nodes to
// cover all unconnected components of a graph
for (int i = 0; i < N; i++)
{
if (discovered[i] == false)
{
// mark the source vertex as discovered
discovered[i] = true;
// enqueue source vertex
q.push(i);
// start BFS traversal from vertex `i`
recursiveBFS(graph, q, discovered);
}
}
return 0;
}
Output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Depth First Search (DFS) – Iterative and Recursive Implementation
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Function to perform DFS traversal on the graph on a graph
void DFS(Graph const &graph, int v, vector<bool> &discovered)
{
// mark the current node as discovered
discovered[v] = true;
// print the current node
cout << v << " ";
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
// if `u` is not yet discovered
if (!discovered[u]) {
DFS(graph, u, discovered);
}
}
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
// Notice that node 0 is unconnected
{1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4},
{3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11}
};
// total number of nodes in the graph (0–12)
int N = 13;
// build a graph from the given edges
Graph graph(edges, N);
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// Perform DFS traversal from all undiscovered nodes to
// cover all unconnected components of a graph
for (int i = 0; i < N; i++)
{
if (discovered[i] == false) {
DFS(graph, i, discovered);
}
}
return 0;
}
Output:
0 1 2 3 4 5 6 7 8 9 10 11 12
Arrival and departure time of vertices in DFS
Given a graph, find the arrival and departure time of its vertices in DFS. The arrival time is the time at which the vertex was explored for the first time in the DFS, and departure time is the time at which we have explored all the neighbors of the vertex, and we are ready to backtrack.
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
}
}
};
// Function to perform DFS traversal on the graph on a graph
int DFS(Graph const &graph, int v, vector<bool> &discovered,
vector<int> &arrival, vector<int> &departure, int &time)
{
// set the arrival time of vertex `v`
arrival[v] = ++time;
// mark vertex as discovered
discovered[v] = true;
for (int i: graph.adjList[v])
{
if (!discovered[i]) {
DFS(graph, i, discovered, arrival, departure, time);
}
}
// set departure time of vertex `v`
departure[v] = ++time;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
{0, 1}, {0, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 5},
{4, 5}, {6, 7}
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph graph(edges, N);
// vector to store the arrival time of vertex
vector<int> arrival(N);
// vector to store the departure time of vertex
vector<int> departure(N);
// Mark all the vertices as not discovered
vector<bool> discovered(N);
int time = -1;
// Perform DFS traversal from all undiscovered nodes to
// cover all unconnected components of a graph
for (int i = 0; i < N; i++)
{
if (!discovered[i]) {
DFS(graph, i, discovered, arrival, departure, time);
}
}
// print arrival and departure time of each
// vertex in DFS
for (int i = 0; i < N; i++)
{
cout << "Vertex " << i << " (" << arrival[i]<< ", " << departure[i] << ")"<< endl;
}
return 0;
}
Output:
Vertex 0 (0, 11)
Vertex 1 (1, 2)
Vertex 2 (3, 10)
Vertex 3 (4, 7)
Vertex 4 (8, 9)
Vertex 5 (5, 6)
Vertex 6 (12, 15)
Vertex 7 (13, 14)
Bipartite Graph
Given a graph, check if it is bipartite or not. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Perform BFS on the graph starting from vertex `v`
bool BFS(Graph const &graph, int v, int N)
{
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// stores the level of each vertex in BFS
vector<int> level(N);
// mark the source vertex as discovered and
// set its level to 0
discovered[v] = true, level[v] = 0;
// create a queue to do BFS and enqueue
// source vertex in it
queue<int> q;
q.push(v);
// loop till queue is empty
while (!q.empty())
{
// dequeue front node
v = q.front();
q.pop()
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
// if vertex `u` is explored for the first time
if (!discovered[u])
{
// mark it as discovered
discovered[u] = true;
// set level one more than the level of the parent node
level[u] = level[v] + 1;
// enqueue vertex
q.push(u);
}
// if the vertex has already been discovered and the
// level of vertex `u` and `v` are the same, then the
// graph contains an odd-cycle and is not bipartite
else if (level[v] == level[u]) {
return false;
}
}
}
return true;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
{1, 2}, {2, 3}, {2, 8}, {3, 4}, {4, 6}, {5, 7},
{5, 9}, {8, 9}
// if we add edge `2 —> 4`, the graph becomes non-bipartite
};
// total number of nodes in the graph
int N = 10;
// build a graph from the given edges
Graph graph(edges, N);
// Perform BFS traversal starting from vertex 1
if (BFS(graph, 1, N)) {
cout << "The graph is bipartite";
}
else {
cout << "The graph is not bipartite";
}
return 0;
}
Output:
The graph is bipartite
Given a Directed Acyclic Graph (DAG), print it in topological order using topological sort algorithm. If the DAG has more than one topological ordering, output any of them
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
}
}
};
// Perform DFS on the graph and set the departure time of all
// vertices of the graph
void DFS(Graph const &graph, int v, vector<bool>
&discovered, vector<int> &departure, int &time)
{
// mark the current node as discovered
discovered[v] = true;
// set the arrival time of vertex `v`
time++;
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
// if `u` is not yet discovered
if (!discovered[u]) {
DFS(graph, u, discovered, departure, time);
}
}
// ready to backtrack
// set departure time of vertex `v`
departure[time] = v;
time++;
}
// Function to perform a topological sort on a given DAG
void doTopologicalSort(Graph const &graph, int N)
{
// `departure[]` stores the vertex number using departure time as an index
vector<int> departure(2*N, -1);
/* If we had done it the other way around, i.e., fill the array with departure time using vertex number as an index, we would need to sort it later */
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
int time = 0;
// perform DFS on all undiscovered vertices
for (int i = 0; i < N; i++)
{
if (!discovered[i]) {
DFS(graph, i, discovered, departure, time);
}
}
// Print the vertices in order of their decreasing
// departure time in DFS, i.e., in topological order
for (int i = 2*N - 1; i >= 0; i--)
{
if (departure[i] != -1) {
cout << departure[i] << " ";
}
}
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges =
{
{0, 6}, {1, 2}, {1, 4}, {1, 6}, {3, 0}, {3, 4},
{5, 1}, {7, 0}, {7, 1}
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph graph(edges, N);
// perform topological sort
doTopologicalSort(graph, N);
return 0;
}
Output:
7 5 3 1 4 2 0 6
Kahn’s Topological Sort Algorithm
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// stores indegree of a vertex
vector<int> indegree;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// initialize indegree
vector<int> temp(N, 0);
indegree = temp;
// add edges to the directed graph
for (auto &edge: edges)
{
// add an edge from source to destination
adjList[edge.src].push_back(edge.dest);
// increment in-degree of destination vertex by 1
indegree[edge.dest]++;
}
}
};
// Function to perform a topological sort on a given DAG
bool doTopologicalSort(Graph const &graph, vector<int> &L, int N)
{
vector<int> indegree = graph.indegree;
// Set of all nodes with no incoming edges
vector<int> S;
for (int i = 0; i < N; i++)
{
if (!indegree[i]) {
S.push_back(i);
}
}
while (!S.empty())
{
// remove node `n` from `S`
int n = S.back();
S.pop_back();
// add `n` at the tail of `L`
L.push_back(n);
for (int m: graph.adjList[n])
{
// remove an edge from `n` to `m` from the graph
indegree[m] -= 1;
// if `m` has no other incoming edges, insert `m` into `S`
if (!indegree[m]) {
S.push_back(m);
}
}
}
// if a graph has edges, then the graph has at least one cycle
for (int i = 0; i < N; i++)
{
if (indegree[i]) {
return false;
}
}
return true;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges =
{ { 0, 6 }, { 1, 2 }, { 1, 4 }, { 1, 6 }, { 3, 0 }, { 3, 4 },
{ 5, 1 }, { 7, 0 }, { 7, 1 }
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph graph(edges, N);
// create an empty vector that will contain the sorted elements
vector<int> L;
// Perform topological sort
if (doTopologicalSort(graph, L, N))
{
// print topological order
for (int i: L) {
cout << i << " ";
}
}
else {
cout << "Graph has at least one cycle. "
"Topological sorting is not possible";
}
return 0;
}
Output:
7 5 1 2 3 4 0 6
Given a connected undirected graph, find if it contains any cycle or not
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Node to store vertex and its parent info in BFS
struct Node {
int v, parent;
};
// Perform BFS on the graph starting from vertex `src` and
// return true if a cycle is found in the graph
bool BFS(Graph const &graph, int src, int N)
{
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// mark the source vertex as discovered
discovered[src] = true;
// create a queue for doing BFS and
// enqueue source vertex
queue<Node> q;
q.push({src, -1});
// loop till queue is empty
while (!q.empty())
{
// dequeue front node and print it
Node node = q.front();
q.pop();
// do for every edge `v —> u`
for (int u: graph.adjList[node.v])
{
if (!discovered[u])
{
// mark it as discovered
discovered[u] = true;
// construct the queue node containing info
// about vertex and enqueue it
q.push({ u, node.v });
}
// `u` is discovered, and `u` is not a parent
else if (u != node.parent)
{
// we found a cross-edge, i.e., the cycle is found
return true;
}
}
}
// no cross-edges were found in the graph
return false;
}
int main()
{
// initialize edges as per the above diagram
vector<Edge> edges =
{
{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {5, 9},
{5, 10}, {4, 7}, {4, 8}, {7, 11}, {7, 12}, {6, 10}
// edge `6 —> 10` introduces a cycle in the graph
};
// total number of nodes in the graph
int N = 13;
// build a graph from the given edges
Graph graph(edges, N);
// Perform BFS traversal in connected components of a graph
if (BFS(graph, 1, N)) {
cout << "The graph contains a cycle";
}
else {
cout << "The graph doesn't contain any cycle";
}
return 0;
}
Output:
The graph contains a cycle
Given a digraph (directed graph), find the total number of routes to reach the destination from a given source with exactly m edges.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
}
}
};
// A BFS Node
struct Node
{
// stores current vertex number and the current depth of
// BFS (how far away from the source current node is)
int vertex, depth;
};
// Perform BFS on graph `g` starting from vertex `v`
int modifiedBFS(Graph const &g, int src, int dest, int m)
{
// create a queue for doing BFS
queue<Node> q;
// enqueue source vertex
q.push({src, 0});
// stores number of paths from source to destination
// having exactly `m` edges
int count = 0;
// loop till queue is empty
while (!q.empty())
{
// dequeue front node
Node node = q.front();
q.pop();
int v = node.vertex;
int depth = node.depth;
// if the destination is reached and BFS depth is equal to `m`,
// update count
if (v == dest && depth == m) {
count++;
}
// don't consider nodes having a BFS depth more than `m`.
// This check will result in optimized code and
// handle cycles in the graph (otherwise, the loop will never break)
if (depth > m) {
break;
}
// do for every adjacent vertex `u` of `v`
for (int u: g.adjList[v])
{
// enqueue every vertex (discovered or undiscovered)
q.push({u, depth + 1});
}
}
// return number of paths from source to destination
return count;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges =
{
{0, 6}, {0, 1}, {1, 6}, {1, 5}, {1, 2}, {2, 3}, {3, 4},
{5, 2}, {5, 3}, {5, 4}, {6, 5}, {7, 6}, {7, 1}
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph g(edges, N);
int src = 0, dest = 3, m = 4;
// Do modified BFS traversal from the source vertex src
cout << modifiedBFS(g, src, dest, m);
return 0;
}
Output:
3
Given an undirected graph, check if it is a tree or not. In other words, check if a given undirected graph is an Acyclic Connected Graph or not
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Perform DFS on the graph and returns true if any back-edge
// is found in the graph
bool DFS(Graph const &graph, int v, vector<bool> &discovered, int parent)
{
// mark the current node as discovered
discovered[v] = true;
// do for every edge `v —> w`
for (int w: graph.adjList[v])
{
// if `w` is not discovered
if (!discovered[w])
{
if (!DFS(graph, w, discovered, v)) {
return false;
}
}
// if `w` is discovered, and `w` is not a parent
else if (w != parent)
{
// we found a back-edge (cycle)
return false;
}
}
// no back-edges were found in the graph
return true;
}
int main()
{
// initialize edges as per the above diagram
vector<Edge> edges =
{
{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 0}
// edge `5 —> 0` introduces a cycle in the graph
};
// total number of nodes in the graph
int N = 6;
// build a graph from the given edges
Graph graph(edges, N);
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// boolean flag to store if the graph is tree or not
bool isTree = true;
// Perform DFS traversal from the first vertex
isTree = DFS(graph, 0, discovered, -1);
for (int i = 0; isTree && i < N; i++)
{
// any undiscovered vertex means the graph is disconnected
if (!discovered[i]) {
isTree = false;
}
}
if (isTree) {
cout << "The graph is a tree";
}
else {
cout << "The graph is not a tree";
}
return 0;
}
Output:
The graph is not a tree
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges)
{
// insert at the end
adjList[edge.src].push_back(edge.dest);
// uncomment the following code for undirected graph
// adjList[edge.dest].push_back(edge.src);
}
}
};
// Function to print adjacency list representation of a graph
void printGraph(Graph const &graph, int N)
{
for (int i = 0; i < N; i++)
{
// print the current vertex number
cout << i << " ——> ";
// print all neighboring vertices of a vertex `i`
for (int v: graph.adjList[i]) {
cout << v << " ";
}
cout << endl;
}
}
// Graph Implementation using STL
int main()
{
// vector of graph edges as per the above diagram.
// Please note that the initialization vector in the below format will
// work fine in C++11, C++14, C++17 but will fail in C++98.
vector<Edge> edges =
{
{ 0, 1}, { 1, 2 }, { 2, 0 }, { 2, 1 },
{ 3, 2 }, { 4, 5 }, { 5, 4 }
};
// total number of nodes in the graph
int N = 6;
// construct graph
Graph graph(edges, N);
// print adjacency list representation of a graph
printGraph(graph, N);
return 0;
}
Output:
(0, 1, 6)
(1, 2, 7)
(2, 0, 5) (2, 1, 4)
(3, 2, 10)
(4, 5, 3)
(5, 4, 1)
Breadth-First Search (BFS) – Iterative and Recursive Implementation
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Perform BFS recursively on the graph
void recursiveBFS(Graph const &graph, queue<int> &q,
vector<bool> &discovered)
{
if (q.empty()) {
return;
}
// dequeue front node and print it
int v = q.front();
q.pop();
cout << v << " ";
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
if (!discovered[u])
{
// mark it as discovered and enqueue it
discovered[u] = true;
q.push(u);
}
}
recursiveBFS(graph, q, discovered);
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {5, 9},
{5, 10}, {4, 7}, {4, 8}, {7, 11}, {7, 12}
// vertex 0, 13, and 14 are single nodes
};
// total number of nodes in the graph
int N = 15;
// build a graph from the given edges
Graph graph(edges, N);
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N, false);
// create a queue for doing BFS
queue<int> q;
// Perform BFS traversal from all undiscovered nodes to
// cover all unconnected components of a graph
for (int i = 0; i < N; i++)
{
if (discovered[i] == false)
{
// mark the source vertex as discovered
discovered[i] = true;
// enqueue source vertex
q.push(i);
// start BFS traversal from vertex `i`
recursiveBFS(graph, q, discovered);
}
}
return 0;
}
Output:
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Depth First Search (DFS) – Iterative and Recursive Implementation
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Function to perform DFS traversal on the graph on a graph
void DFS(Graph const &graph, int v, vector<bool> &discovered)
{
// mark the current node as discovered
discovered[v] = true;
// print the current node
cout << v << " ";
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
// if `u` is not yet discovered
if (!discovered[u]) {
DFS(graph, u, discovered);
}
}
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
// Notice that node 0 is unconnected
{1, 2}, {1, 7}, {1, 8}, {2, 3}, {2, 6}, {3, 4},
{3, 5}, {8, 9}, {8, 12}, {9, 10}, {9, 11}
};
// total number of nodes in the graph (0–12)
int N = 13;
// build a graph from the given edges
Graph graph(edges, N);
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// Perform DFS traversal from all undiscovered nodes to
// cover all unconnected components of a graph
for (int i = 0; i < N; i++)
{
if (discovered[i] == false) {
DFS(graph, i, discovered);
}
}
return 0;
}
Output:
0 1 2 3 4 5 6 7 8 9 10 11 12
Arrival and departure time of vertices in DFS
Given a graph, find the arrival and departure time of its vertices in DFS. The arrival time is the time at which the vertex was explored for the first time in the DFS, and departure time is the time at which we have explored all the neighbors of the vertex, and we are ready to backtrack.
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
}
}
};
// Function to perform DFS traversal on the graph on a graph
int DFS(Graph const &graph, int v, vector<bool> &discovered,
vector<int> &arrival, vector<int> &departure, int &time)
{
// set the arrival time of vertex `v`
arrival[v] = ++time;
// mark vertex as discovered
discovered[v] = true;
for (int i: graph.adjList[v])
{
if (!discovered[i]) {
DFS(graph, i, discovered, arrival, departure, time);
}
}
// set departure time of vertex `v`
departure[v] = ++time;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
{0, 1}, {0, 2}, {2, 3}, {2, 4}, {3, 1}, {3, 5},
{4, 5}, {6, 7}
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph graph(edges, N);
// vector to store the arrival time of vertex
vector<int> arrival(N);
// vector to store the departure time of vertex
vector<int> departure(N);
// Mark all the vertices as not discovered
vector<bool> discovered(N);
int time = -1;
// Perform DFS traversal from all undiscovered nodes to
// cover all unconnected components of a graph
for (int i = 0; i < N; i++)
{
if (!discovered[i]) {
DFS(graph, i, discovered, arrival, departure, time);
}
}
// print arrival and departure time of each
// vertex in DFS
for (int i = 0; i < N; i++)
{
cout << "Vertex " << i << " (" << arrival[i]<< ", " << departure[i] << ")"<< endl;
}
return 0;
}
Output:
Vertex 0 (0, 11)
Vertex 1 (1, 2)
Vertex 2 (3, 10)
Vertex 3 (4, 7)
Vertex 4 (8, 9)
Vertex 5 (5, 6)
Vertex 6 (12, 15)
Vertex 7 (13, 14)
Bipartite Graph
Given a graph, check if it is bipartite or not. A bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Perform BFS on the graph starting from vertex `v`
bool BFS(Graph const &graph, int v, int N)
{
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// stores the level of each vertex in BFS
vector<int> level(N);
// mark the source vertex as discovered and
// set its level to 0
discovered[v] = true, level[v] = 0;
// create a queue to do BFS and enqueue
// source vertex in it
queue<int> q;
q.push(v);
// loop till queue is empty
while (!q.empty())
{
// dequeue front node
v = q.front();
q.pop()
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
// if vertex `u` is explored for the first time
if (!discovered[u])
{
// mark it as discovered
discovered[u] = true;
// set level one more than the level of the parent node
level[u] = level[v] + 1;
// enqueue vertex
q.push(u);
}
// if the vertex has already been discovered and the
// level of vertex `u` and `v` are the same, then the
// graph contains an odd-cycle and is not bipartite
else if (level[v] == level[u]) {
return false;
}
}
}
return true;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges = {
{1, 2}, {2, 3}, {2, 8}, {3, 4}, {4, 6}, {5, 7},
{5, 9}, {8, 9}
// if we add edge `2 —> 4`, the graph becomes non-bipartite
};
// total number of nodes in the graph
int N = 10;
// build a graph from the given edges
Graph graph(edges, N);
// Perform BFS traversal starting from vertex 1
if (BFS(graph, 1, N)) {
cout << "The graph is bipartite";
}
else {
cout << "The graph is not bipartite";
}
return 0;
}
Output:
The graph is bipartite
Given a Directed Acyclic Graph (DAG), print it in topological order using topological sort algorithm. If the DAG has more than one topological ordering, output any of them
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
}
}
};
// Perform DFS on the graph and set the departure time of all
// vertices of the graph
void DFS(Graph const &graph, int v, vector<bool>
&discovered, vector<int> &departure, int &time)
{
// mark the current node as discovered
discovered[v] = true;
// set the arrival time of vertex `v`
time++;
// do for every edge `v —> u`
for (int u: graph.adjList[v])
{
// if `u` is not yet discovered
if (!discovered[u]) {
DFS(graph, u, discovered, departure, time);
}
}
// ready to backtrack
// set departure time of vertex `v`
departure[time] = v;
time++;
}
// Function to perform a topological sort on a given DAG
void doTopologicalSort(Graph const &graph, int N)
{
// `departure[]` stores the vertex number using departure time as an index
vector<int> departure(2*N, -1);
/* If we had done it the other way around, i.e., fill the array with departure time using vertex number as an index, we would need to sort it later */
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
int time = 0;
// perform DFS on all undiscovered vertices
for (int i = 0; i < N; i++)
{
if (!discovered[i]) {
DFS(graph, i, discovered, departure, time);
}
}
// Print the vertices in order of their decreasing
// departure time in DFS, i.e., in topological order
for (int i = 2*N - 1; i >= 0; i--)
{
if (departure[i] != -1) {
cout << departure[i] << " ";
}
}
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges =
{
{0, 6}, {1, 2}, {1, 4}, {1, 6}, {3, 0}, {3, 4},
{5, 1}, {7, 0}, {7, 1}
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph graph(edges, N);
// perform topological sort
doTopologicalSort(graph, N);
return 0;
}
Output:
7 5 3 1 4 2 0 6
Kahn’s Topological Sort Algorithm
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// stores indegree of a vertex
vector<int> indegree;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// initialize indegree
vector<int> temp(N, 0);
indegree = temp;
// add edges to the directed graph
for (auto &edge: edges)
{
// add an edge from source to destination
adjList[edge.src].push_back(edge.dest);
// increment in-degree of destination vertex by 1
indegree[edge.dest]++;
}
}
};
// Function to perform a topological sort on a given DAG
bool doTopologicalSort(Graph const &graph, vector<int> &L, int N)
{
vector<int> indegree = graph.indegree;
// Set of all nodes with no incoming edges
vector<int> S;
for (int i = 0; i < N; i++)
{
if (!indegree[i]) {
S.push_back(i);
}
}
while (!S.empty())
{
// remove node `n` from `S`
int n = S.back();
S.pop_back();
// add `n` at the tail of `L`
L.push_back(n);
for (int m: graph.adjList[n])
{
// remove an edge from `n` to `m` from the graph
indegree[m] -= 1;
// if `m` has no other incoming edges, insert `m` into `S`
if (!indegree[m]) {
S.push_back(m);
}
}
}
// if a graph has edges, then the graph has at least one cycle
for (int i = 0; i < N; i++)
{
if (indegree[i]) {
return false;
}
}
return true;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges =
{ { 0, 6 }, { 1, 2 }, { 1, 4 }, { 1, 6 }, { 3, 0 }, { 3, 4 },
{ 5, 1 }, { 7, 0 }, { 7, 1 }
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph graph(edges, N);
// create an empty vector that will contain the sorted elements
vector<int> L;
// Perform topological sort
if (doTopologicalSort(graph, L, N))
{
// print topological order
for (int i: L) {
cout << i << " ";
}
}
else {
cout << "Graph has at least one cycle. "
"Topological sorting is not possible";
}
return 0;
}
Output:
7 5 1 2 3 4 0 6
Given a connected undirected graph, find if it contains any cycle or not
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Node to store vertex and its parent info in BFS
struct Node {
int v, parent;
};
// Perform BFS on the graph starting from vertex `src` and
// return true if a cycle is found in the graph
bool BFS(Graph const &graph, int src, int N)
{
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// mark the source vertex as discovered
discovered[src] = true;
// create a queue for doing BFS and
// enqueue source vertex
queue<Node> q;
q.push({src, -1});
// loop till queue is empty
while (!q.empty())
{
// dequeue front node and print it
Node node = q.front();
q.pop();
// do for every edge `v —> u`
for (int u: graph.adjList[node.v])
{
if (!discovered[u])
{
// mark it as discovered
discovered[u] = true;
// construct the queue node containing info
// about vertex and enqueue it
q.push({ u, node.v });
}
// `u` is discovered, and `u` is not a parent
else if (u != node.parent)
{
// we found a cross-edge, i.e., the cycle is found
return true;
}
}
}
// no cross-edges were found in the graph
return false;
}
int main()
{
// initialize edges as per the above diagram
vector<Edge> edges =
{
{1, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}, {5, 9},
{5, 10}, {4, 7}, {4, 8}, {7, 11}, {7, 12}, {6, 10}
// edge `6 —> 10` introduces a cycle in the graph
};
// total number of nodes in the graph
int N = 13;
// build a graph from the given edges
Graph graph(edges, N);
// Perform BFS traversal in connected components of a graph
if (BFS(graph, 1, N)) {
cout << "The graph contains a cycle";
}
else {
cout << "The graph doesn't contain any cycle";
}
return 0;
}
Output:
The graph contains a cycle
Given a digraph (directed graph), find the total number of routes to reach the destination from a given source with exactly m edges.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the directed graph
for (auto &edge: edges) {
adjList[edge.src].push_back(edge.dest);
}
}
};
// A BFS Node
struct Node
{
// stores current vertex number and the current depth of
// BFS (how far away from the source current node is)
int vertex, depth;
};
// Perform BFS on graph `g` starting from vertex `v`
int modifiedBFS(Graph const &g, int src, int dest, int m)
{
// create a queue for doing BFS
queue<Node> q;
// enqueue source vertex
q.push({src, 0});
// stores number of paths from source to destination
// having exactly `m` edges
int count = 0;
// loop till queue is empty
while (!q.empty())
{
// dequeue front node
Node node = q.front();
q.pop();
int v = node.vertex;
int depth = node.depth;
// if the destination is reached and BFS depth is equal to `m`,
// update count
if (v == dest && depth == m) {
count++;
}
// don't consider nodes having a BFS depth more than `m`.
// This check will result in optimized code and
// handle cycles in the graph (otherwise, the loop will never break)
if (depth > m) {
break;
}
// do for every adjacent vertex `u` of `v`
for (int u: g.adjList[v])
{
// enqueue every vertex (discovered or undiscovered)
q.push({u, depth + 1});
}
}
// return number of paths from source to destination
return count;
}
int main()
{
// vector of graph edges as per the above diagram
vector<Edge> edges =
{
{0, 6}, {0, 1}, {1, 6}, {1, 5}, {1, 2}, {2, 3}, {3, 4},
{5, 2}, {5, 3}, {5, 4}, {6, 5}, {7, 6}, {7, 1}
};
// total number of nodes in the graph
int N = 8;
// build a graph from the given edges
Graph g(edges, N);
int src = 0, dest = 3, m = 4;
// Do modified BFS traversal from the source vertex src
cout << modifiedBFS(g, src, dest, m);
return 0;
}
Output:
3
Given an undirected graph, check if it is a tree or not. In other words, check if a given undirected graph is an Acyclic Connected Graph or not
#include <iostream>
#include <vector>
using namespace std;
// Data structure to store a graph edge
struct Edge {
int src, dest;
};
// A class to represent a graph object
class Graph
{
public:
// a vector of vectors to represent an adjacency list
vector<vector<int>> adjList;
// Graph Constructor
Graph(vector<Edge> const &edges, int N)
{
// resize the vector to hold `N` elements of type `vector<int>`
adjList.resize(N);
// add edges to the undirected graph
for (auto &edge: edges)
{
adjList[edge.src].push_back(edge.dest);
adjList[edge.dest].push_back(edge.src);
}
}
};
// Perform DFS on the graph and returns true if any back-edge
// is found in the graph
bool DFS(Graph const &graph, int v, vector<bool> &discovered, int parent)
{
// mark the current node as discovered
discovered[v] = true;
// do for every edge `v —> w`
for (int w: graph.adjList[v])
{
// if `w` is not discovered
if (!discovered[w])
{
if (!DFS(graph, w, discovered, v)) {
return false;
}
}
// if `w` is discovered, and `w` is not a parent
else if (w != parent)
{
// we found a back-edge (cycle)
return false;
}
}
// no back-edges were found in the graph
return true;
}
int main()
{
// initialize edges as per the above diagram
vector<Edge> edges =
{
{0, 1}, {1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 0}
// edge `5 —> 0` introduces a cycle in the graph
};
// total number of nodes in the graph
int N = 6;
// build a graph from the given edges
Graph graph(edges, N);
// to keep track of whether a vertex is discovered or not
vector<bool> discovered(N);
// boolean flag to store if the graph is tree or not
bool isTree = true;
// Perform DFS traversal from the first vertex
isTree = DFS(graph, 0, discovered, -1);
for (int i = 0; isTree && i < N; i++)
{
// any undiscovered vertex means the graph is disconnected
if (!discovered[i]) {
isTree = false;
}
}
if (isTree) {
cout << "The graph is a tree";
}
else {
cout << "The graph is not a tree";
}
return 0;
}
Output:
The graph is not a tree
