Topic- Graph
Just simplified my experience here…
Hope it goona help you all… @himanshu_shekhar16
Save this pdf and thanks me later @himanshushekar
Reference taken form GFG, Leetcode, and InterviewBit
Part 1: Link
What is Graph in Data Structure and Algorithms?
A Graph is a non-linear data structure consisting of vertices and edges. The vertices are sometimes
also referred to as nodes and the edges are lines or arcs that connect any two nodes in the graph. More
formally a Graph is composed of a set of vertices( V ) and a set of edges( E ). The graph is denoted by
G(E, V).
Components of a Graph
Vertices: Vertices are the fundamental units of the graph. Sometimes, vertices are also known as vertex or
nodes. Every node/vertex can be labeled or unlabelled.
Edges: Edges are drawn or used to connect two nodes of the graph. It can be ordered pair of nodes in a
directed graph. Edges can connect any two nodes in any possible way. There are no rules. Sometimes,
edges are also known as arcs. Every edge can be labeled/unlabelled.
Graphs are used to solve many real-life problems. Graphs are used to represent networks. The
networks may include paths in a city or telephone network or circuit network. Graphs are also used in
social networks like linkedIn, Facebook. For example, in Facebook, each person is represented with a
vertex(or node). Each node is a structure and contains information like person id, name, gender, locale
etc.
DFS and BFS
#include <bits/stdc++.h>
using namespace std;
vector<bool> visited;
void dfs(int node, vector<vector<int>> &v)
// preorder
visited[node] = true;
cout<<node<<" ";
vector<int> :: iterator it;
for(it=v[node].begin(); it!= v[node].end(); it++)
if(visited[*it] == false)
dfs(*it, v);
// postorder
// cout<<node<<" ";
void bfs(int node, vector<vector<int>> &v)
queue<int> pq;
pq.push(node);
visited[node] = true;
while(!pq.empty())
int t= pq.front();
pq.pop();
cout<<t<<" ";
vector<int> :: iterator it;
for( it = v[t].begin(); it!=v[t].end(); it++)
if(visited[*it]);
else{
visited[*it] = true;
pq.push(*it);
int main()
int n, m;
cin >> n >> m;
vector<vector<int>> v(n);
visited = vector<bool> (n, 0);
for(int i=0; i<m; i++)
{
int x, y;
cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
dfs(0, v);
cout<<endl;
visited = vector<bool>(n, 0);
bfs(0, v);
return 0;
Best Problems on Graph (DFS/BFS)
Create a Graph, print it
Find the smallest binary digit multiple of given number
Roots of a tree which give minimum height
Stepping Numbers
Check if two nodes are on same path in a tree
A matrix probability question
Detect Cycle in a Directed Graph
Detect cycle in an undirected graph
Detect cycle in a direct graph using colors
Dijkstra’s shortest path algorithm
Dijkstra’s Algorithm for Adjacency List Representation
Bellman–Ford Algorithm
Floyd Warshall Algorithm
Johnson’s algorithm for All-pairs shortest paths
Shortest Path in Directed Acyclic Graph
Shortest path with exactly k edges in a directed and weighted graph
Dial’s Algorithm
Printing paths in Dijsktra’s Algorithm
Implement BFS algorithm
Implement DFS Algo
Detect Cycle in Directed Graph using BFS/DFS Algo
Detect Cycle in UnDirected Graph using BFS/DFS Algo
Search in a Maze
Minimum Step by Knight
flood fill algo
Clone a graph
Making wired Connections
word Ladder
Dijkstra algo
Implement Topological Sort
Minimum time taken by each job to be completed given by a Directed Acyclic Graph
Find whether it is possible to finish all tasks or not from given dependencies
Find the no. of Isalnds
Given a sorted Dictionary of an Alien Language, find order of characters
Implement Kruksal’sAlgorithm
Implement Prim’s Algorithm
Total no. of Spanning tree in a graph
Implement Bellman Ford Algorithm
Implement Floyd warshallAlgorithm
Travelling Salesman Problem
Graph ColouringProblem
Snake and Ladders Problem
Find bridge in a graph
Count Strongly connected Components(Kosaraju Algo)
Check whether a graph is Bipartite or Not
Detect Negative cycle in a graph
Longest path in a Directed Acyclic Graph
Journey to the Moon
Cheapest Flights Within K Stops
Oliver and the Game
Water Jug problem using BFS
Water Jug problem using BFS
Find if there is a path of more thank length from a source
M-ColouringProblem
Minimum edges to reverse o make path from source to destination
Paths to travel each nodes using each edge(Seven Bridges)
Vertex Cover Problem
Chinese Postman or Route Inspection
Number of Triangles in a Directed and Undirected Graph
Minimise the cashflow among a given set of friends who have borrowed money from each
Two Clique Problem
Breadth First Traversal for a Graph
Depth First Traversal for a Graph
Applications of Depth First Search
Applications of Breadth First Traversal
Graph representations using set and hash
Find Mother Vertex in a Graph
Transitive Closure of a Graph using DFS
Find K cores of an undirected Graph
Iterative Depth First Search
Count the number of nodes at given level in a tree using BFS
Count all possible paths between two vertices
Minimum initial vertices to traverse whole matrix with given conditions
Shortest path to reach one prime to other by changing single digit at a time
Water Jug problem using BFS
Count number of trees in a forest
BFS using vectors & queue as per the algorithm of CLRS
Level of Each node in a Tree from source node
Construct binary palindrome by repeated appending and trimming
Transpose graph
Path in a Rectangle with Circles
Height of a generic tree from parent array
BFS using STL for competitive coding
DFS for a n-ary tree (acyclic graph) represented as adjacency list
Maximum number of edges to be added to a tree so that it stays a Bipartite graph
A Peterson Graph Problem
Implementation of Graph in JavaScript
Print all paths from a given source to a destination using BFS
Minimum number of edges between two vertices of a Graph
Count nodes within K-distance from all nodes in a set
Bidirectional Search
Minimum edge reversals to make a root
BFS for Disconnected Graph
Move weighting scale alternate under given constraints
Best First Search (Informed Search)
Minimum steps to reach target by a Knight | Set 1
Minimum number of operation required to convert number x into y
Minimum steps to reach end of array under constraints
Feel Free to connect with me –
https://www.linkedin.com/in/himanshushekhar16/
