Graph Its Implementation And Some popular BFS/DFS Problems…..
Medium Article For Better Redability.......
In simple language, a graph is a collection of dots (called vertices) connected by lines (called edges). These dots represent objects, and the lines represent relationships between those objects. Graphs are used to model various real-world scenarios, like social networks, road networks, or connections between computers. They are essential in solving problems involving connections and dependencies between different elements.
Definitions and Terminology:
1. Vertices (Nodes): These are the individual elements or entities in the graph. Each vertex can hold data associated with it, known as the vertex's "payload."
2. Edges: These are the connections or relationships between pairs of vertices. An edge connects two vertices and may have an optional weight or cost associated with it, representing some quantitative value or distance.
3. Path: Path is a sequence of vertices connected by edges, which allows you to move from one vertex to another in the graph. It represents a route or a series of steps that you can take to traverse the graph from a starting vertex to an ending vertex, passing through intermediate vertices (if any) along the way.
4. Edge Weight: Edge weight refers to a numerical value assigned to an edge in a weighted graph. Weighted graphs are graphs where each edge has an associated weight or cost
5. Degree: The degree of a vertex in a graph is a measure of the number of edges incident to that vertex. In other words, it tells us how many edges are connected to a specific vertex.
Key points about vertex degree:
1. Degree of a Vertex: For an undirected graph, the degree of a vertex is the count of edges connected to that vertex. In a directed graph, the degree of a vertex is the sum of its in-degree (incoming edges) and out-degree (outgoing edges).
2. In-Degree: In a directed graph, the in-degree of a vertex is the number of incoming edges directed towards that vertex.
3. Out-Degree: In a directed graph, the out-degree of a vertex is the number of outgoing edges from that vertex.
4. Self-Loop: If there is an edge connecting a vertex to itself (self-loop), it is counted as one of the incident edges, contributing to the degree of that vertex.
5. Isolated Vertex: A vertex with a degree of 0 is called an isolated vertex, meaning it has no edges incident to it.Types Of Graphs:
Graphs can be classified into various types based on their properties and characteristics. Here are some of the most common types of graphs:
1. Undirected Graph: In an undirected graph, the edges have no direction, meaning the connection between vertices is bidirectional. If there is an edge between vertex A and vertex B, you can traverse it in both directions, from A to B and from B to A.
2. Directed Graph: In a directed graph, each edge has a direction associated with it. This means that the relationship between two vertices is one-way. If there is a directed edge from vertex A to vertex B, you can only traverse it from A to B and not vice versa.
3. Weighted Graph: A graph in which each edge has an associated weight or cost, typically representing some numerical value, distance, or cost.
4. Unweighted Graph: A graph in which all edges have the same weight, usually considered to be 1. The specific weights are not significant in this type of graph.
6. Cyclic Graph: A graph that contains at least one cycle, which is a closed path that starts and ends at the same vertex, passing through one or more vertices.
7. Acyclic Graph: A graph that does not contain any cycles. It is a special type of graph with no closed loops.
8. Connected Graph: A graph where there is a path between every pair of vertices. All vertices are reachable from any other vertex through a sequence of edges.
9. Disconnected Graph: A graph that contains multiple connected components, where some vertices are not reachable from others.
Graph Representation:
There are two common ways to represent a graph:
1. Adjacency Matrix: In this representation, a 2D matrix is used to show the connections between nodes. The rows and columns of the matrix correspond to the nodes in the graph, and the value in the matrix cell represents whether there is an edge between the nodes or not. Typically, a 1 indicates an edge, while a 0 indicates no edge.
Example: Four nodes (A, B, C, D) and five edges (AB, AC, AD, BC, CD):
A B C D
A 0 1 1 1
B 1 0 1 0
C 1 1 0 1
D 1 0 1 0For directed graphs, the matrix may not be symmetric since the edge from node i to node j might be different from the edge from node j to node i.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, u, v;
cin >> n >> m;
int g[n+1][n+1];
for(int i = 0; i < m; i++)
{
cin >> u >> v;
g[u][v] = 1;
g[v][u] = 1 // Skip in case of directed graph
}
return 0;
}2. Adjacency List: In this representation, each node in the graph has a list of its neighboring nodes. It can be implemented using an array or a dictionary where the keys are the nodes, and the associated values are lists containing the neighboring nodes.
Example of an undirected graph with four nodes (A, B, C, D) and five edges (AB, AC, AD, BC, CD):
A: [B, C, D]
B: [A, C]
C: [A, B, D]
D: [A, C]#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, u, v;
cin >> n >> m;
vector<int> g[n+1];
for(int i = 0; i < m; i++)
{
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u); // Skip in case of directed graph
}
return 0;
}
Breadth First Search (BFS):
Algorithm:
1. Pick a starting node push it into the queue, mark it as visited.
2. In every iteration, pop out the 'x' node and put it in the solution vector.
3. All the unvisited adjacent nodes from 'x' are pushed into the queue.
4. Repeat steps 2 and 3.#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> bfsOfGraph(int n, vector<int> adj[]) {
vector<bool>vis(n,0);
// 1. Pick a starting node push it into the queue, mark it as visited.
queue<int>q;
vis[0]=1;
q.push(0);
vector<int>ans;
// 4. Repeat steps 2 and 3.
while(!q.empty()) {
// 2. In every iteration, pop out the 'x' node and put it in the solution vector.
int node = q.front();
q.pop();
ans.push_back(node);
//3. All the unvisited adjacent nodes from 'x' are pushed into the queue.
for(auto a:adj[node]) {
if(!vis[a]) {
vis[a]=1;
q.push(a);
}
}
}
return ans;
}
};Depth First Search (DFS):
1. Start with an initial node as the current node.
2. Mark the current node as visited to keep track of the nodes already explored.
3. Process the current node (e.g., print its value or perform any desired operation).
4. Find an unvisited neighboring node of the current node and make it the new current node.
5. If all neighboring nodes are visited, backtrack to the previous node (pop it from the stack if using an explicit stack).
6. Repeat steps 2 to 5 until there are no more unvisited nodes.class Solution {
public:
void dfs(int node, vector<int>adj[], vector<bool>&vis, vector<int>& ans) {
vis[node] = 1;
ans.push_back(node);
for(auto a:adj[node]) {
if(!vis[a]) {
dfs(a,adj,vis,ans);
}
}
}
// Function to return a list containing the DFS traversal of the graph.
vector<int> dfsOfGraph(int n, vector<int> adj[]) {
vector<bool>vis(n,0);
int s = 0;
vector<int>ans;
dfs(s, adj, vis, ans);
return ans;
}
};
Lets Begin With Some Popular Problems:
1. Number of Provinces
2. Rotten Oranges : Min time to rot all oranges : BFS
3. Flood Fill Algorithm
4. Distance of Nearest Cell having 1
5. Surrounded Regions | Replace O's with X's
6. Number of Enclaves
7. Number of Islands
8. Bipartite Graph
Problem Statement (Click me for Leetcode link): There are n cities. Some of them are connected, while some are not. If city a is connected directly with city b, and city b is connected directly with city c, then city a is connected indirectly with city c.
A province is a group of directly or indirectly connected cities and no other cities outside of the group.
You are given an n x n matrix isConnected where isConnected[i][j] = 1 if the ith city and the jth city are directly connected, and isConnected[i][j] = 0 otherwise.
Return the total number of provinces.
Example:
Explanation:
We can solve this problem with the help of BFS/DFS. So let's think about it:
We can maintain a visited array which represents all the nodes. Mark all the nodes as 0(Unvisited).
Then transverse all the nodes and if that node is unvisited, then consider it as a seprate graph(Provinces), and consider that node as a starting node and traverse that graph using DFS/BFS.
DFS/BFS will help to mark all the nodes in a graph as visited.
At last mantain a counter and count number of time DFS/BFS is called.
class Solution {
public:
void dfs(vector<int>adj[], vector<bool>&vis, int node) {
vis[node]=1;
for(auto a:adj[node]) {
if(!vis[a])dfs(adj,vis,a);
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
// converting adjacent matrix into adjacent list
vector<int>adj[n];
for(int i=0;i<n;i++) {
for(int j=0;j<n;j++) {
if(isConnected[i][j] && i!=j) {
adj[i].push_back(j);
adj[j].push_back(i);
}
}
}
// creating visited array and counter
vector<bool>vis(n,0);
int count = 0;
for(int i=0;i<n;i++) {
if(!vis[i]) {
dfs(adj,vis,i);
count++;
}
}
return count;
}
};
Problem Statment(Click me for Leetcode link): You are given an m x n grid where each cell can have one of three values:
0 representing an empty cell,
1 representing a fresh orange, or
2 representing a rotten orange.
Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.
Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.
Explanation:
According to the problem statement, one rotten orange can cause 4 of its neighbors to rot, and those 4 neighbors, in the second iteration, can then cause their immediate neighbors to rot. This pattern is very similar to BFS. Let's discuss how we can solve this problem using BFS.
Steps:
- First, create a queue to store all the rotten oranges.
- While the queue is not empty, pick a rotten orange from the queue and check in all four directions. If you find a fresh orange, make it rotten and add it to the queue.
- If you rot some oranges during this iteration, increment the day count.
- Repeat this process until queue is empty.
To check whether we have been able to rot all the oranges in the end, maintain a count of the total number of oranges initially and a count of the total number of rotten oranges after the BFS (Breadth-First Search).
If both counts are equal, it indicates that we have been able to rot all the oranges.
class Solution {
public:
// these are utils array to navigate in all four direction
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int orangesRotting(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size();
int time = 0,totalOrg = 0, count = 0;
queue<pair<int,int>>q;
// building a queue for all the starting points.
for(int i = 0; i < m; i++) {
for(int j = 0; j<n; j++) {
if(grid[i][j] != 0) totalOrg+=1;
if(grid[i][j] == 2) q.push({i,j});
}
}
while(!q.empty()) {
int k = q.size();
count += k;
while(k--) {
int x = q.front().first, y = q.front().second;
q.pop();
// technique to traverse in all four direction use pen and paper to understand.
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= m || ny >= n) continue;
// if orange is fresh make it rottan and push it to queue.
if(grid[nx][ny]==1) {
grid[nx][ny] = 2;
q.push({nx,ny});
}
}
}
if(!q.empty())time += 1;
}
// if count of rotten oranges is equal to total oranges then return time.
if(count == totalOrg)return time;
return -1;
}
};
Problem Statment(Click me for Leetcode link): An image is represented by an m x n integer grid image where image[i][j] represents the pixel value of the image.
You are also given three integers sr, sc, and color. You should perform a flood fill on the image starting from the pixel image[sr][sc].
To perform a flood fill, consider the starting pixel, plus any pixels connected 4-directionally to the starting pixel of the same color as the starting pixel, plus any pixels connected 4-directionally to those pixels (also with the same color), and so on. Replace the color of all of the aforementioned pixels with color.
Return the modified image after performing the flood fill.
Explanation:
If you are approaching this problem after solving the "Rotten Oranges" problem, it's likely that you are considering solving it using BFS.
However, there's an important distinction between the two. In the Rotten Oranges problem, the objective is to determine the total time required to rot all the oranges, which imposes specific constraints.
In this problem, however, such constraints are absent. This leads us to the conclusion that we can employ either BFS or DFS.
I am solving this problem using both BFS and DFS for better understanding.
class Solution {
public:
// these are utils array to navigate in all four direction
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vector<vector<int>> dfsAns, bfsAns;
int n, m, initColor, newColor;
void bfs(int r, int c) {
queue<pair<int,int>>q;
q.push({ r, c});
bfsAns[r][c] = newColor;
while(!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
// technique to traverse in all four direction use pen and paper to understand.
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(bfsAns[nx][ny] == initColor && bfsAns[nx][ny] != newColor) {
bfsAns[nx][ny] = newColor;
q.push({nx,ny});
}
}
}
}
void dfs(int r, int c) {
dfsAns[r][c] = newColor;
for(int i = 0; i < 4; i++) {
int nx = r + dx[i], ny = c + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(dfsAns[nx][ny] == initColor && dfsAns[nx][ny] != newColor) {
dfsAns[nx][ny] = newColor;
dfs(nx,ny);
}
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
// building some global variable for code simplicity
dfsAns = image, bfsAns = image;
n = image.size(), m = image[0].size(), initColor = image[sr][sc], newColor = color;
// answer using bfs
bfs(sr,sc);
// answer using dfs
dfs(sr,sc);
return bfsAns; // return dfsAns in case of dfs
}
};
Problem Statment(Click me for Leetcode link): Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.
A region is captured by flipping all 'O's into 'X's in that surrounded region.
Explanation:
Upon careful analysis of the problem, it becomes evident that the boundary elements of the matrix cannot be encompassed by 'X'. As a result, our traversal should initiate from these boundary elements.
We need to identify all the interconnected 'O' through this traversal process. Once the traversal is complete, the remaining 'O' that have not been connected to the boundaries can be replaced with 'X' .
This process will effectively capture and transform the regions enclosed by 'X' into the desired outcome.
We can use both BFS/DFS for this problem.
Steps:
- Create a visited array and initialize it with 0.
- Do the boundry traversal of the matrix given.
- If you find 'O' then call DFS Funtion.
DFS Funtion will run through all the neighboring 'O' in all four direction and mark them as visited. - At last we can calculate our answer based on visited array as all the 1 is 'O' and remaining are 'X' .
class Solution {
public:
// these are utils array to navigate in all four direction
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n,m;
void dfs(int r, int c, vector<vector<bool>> &vis, vector<vector<char>> &board) {
vis[r][c] = 1;
for(int i = 0; i < 4; i++) {
int nx = r + dx[i], ny = c + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(!vis[nx][ny] && board[nx][ny] == 'O') {
dfs(nx, ny, vis, board);
}
}
}
void solve(vector<vector<char>>& board) {
n = board.size(), m = board[0].size();
vector<vector<bool>>vis(n,vector<bool>(m,0));
// boundry traversal column for better understanding use pen and paper
for(int i = 0; i<n; i++) {
if(!vis[i][0] && board[i][0] == 'O') {
dfs(i, 0, vis, board);
}
if(!vis[i][m-1] && board[i][m-1] == 'O') {
dfs(i, m-1, vis, board);
}
}
// boundry traversal row for better understanding use pen and paper
for(int i=0; i<m; i++) {
if(!vis[0][i] && board[0][i] == 'O') {
dfs(0, i, vis, board);
}
if(!vis[n-1][i] && board[n-1][i] == 'O') {
dfs(n-1, i, vis, board);
}
}
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(!vis[i][j]) {
board[i][j] = 'X';
}
}
}
}
};
Problem Statment(Click me for Leetcode link):
You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.
A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.
Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.
Explanation:
This problem is very similar to surrounded region. We can follow the very same approch that we followed in surrounded region problem.
DFS Solution:
class Solution {
public:
// these are utils array to navigate in all four direction
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n,m;
void dfs(int r, int c, vector<vector<bool>> &vis, vector<vector<int>> &grid) {
vis[r][c] = 1;
for(int i = 0; i < 4; i++) {
int nx = r + dx[i], ny = c + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(!vis[nx][ny] && grid[nx][ny] == 1) {
dfs(nx, ny, vis, grid);
}
}
}
int numEnclaves(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
vector<vector<bool>>vis(n,vector<bool>(m,0));
// boundry traversal column for better understanding use pen and paper
for(int i = 0; i<n; i++) {
if(!vis[i][0] && grid[i][0] == 1) {
dfs(i, 0, vis, grid);
}
if(!vis[i][m-1] && grid[i][m-1] == 1) {
dfs(i, m-1, vis, grid);
}
}
// boundry traversal row for better understanding use pen and paper
for(int i=0; i<m; i++) {
if(!vis[0][i] && grid[0][i] == 1) {
dfs(0, i, vis, grid);
}
if(!vis[n-1][i] && grid[n-1][i] == 1) {
dfs(n-1, i, vis, grid);
}
}
int ans = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(!vis[i][j] && grid[i][j] == 1) {
ans += 1;;
}
}
}
return ans;
}
};BFS Solution:
class Solution {
public:
// these are utils array to navigate in all four direction
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
int n,m;
void dfs(int r, int c, vector<vector<bool>> &vis, vector<vector<int>> &grid) {
vis[r][c] = 1;
for(int i = 0; i < 4; i++) {
int nx = r + dx[i], ny = c + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(!vis[nx][ny] && grid[nx][ny] == 1) {
dfs(nx, ny, vis, grid);
}
}
}
int numEnclaves(vector<vector<int>>& grid) {
n = grid.size(), m = grid[0].size();
vector<vector<bool>>vis(n,vector<bool>(m,0));
queue<pair<int,int>>q;
// boundry traversal column for better understanding use pen and paper
for(int i = 0; i<n; i++) {
if(!vis[i][0] && grid[i][0] == 1) {
vis[i][0] = 1;
q.push({i,0});
}
if(!vis[i][m-1] && grid[i][m-1] == 1) {
vis[i][m-1] = 1;
q.push({i,m-1});
}
}
// boundry traversal row for better understanding use pen and paper
for(int i=0; i<m; i++) {
if(!vis[0][i] && grid[0][i] == 1) {
vis[0][i] = 1;
q.push({0,i});
}
if(!vis[n-1][i] && grid[n-1][i] == 1) {
vis[n-1][i] = 1;
q.push({n-1,i});
}
}
while(!q.empty()) {
int x = q.front().first, y = q.front().second;
q.pop();
for(int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if(nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
if(!vis[nx][ny] && grid[nx][ny] == 1) {
vis[nx][ny] = 1;
q.push({nx,ny});
}
}
}
int ans = 0;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
if(!vis[i][j] && grid[i][j] == 1) {
ans += 1;
}
}
}
return ans;
}
};
Problem Statment(Click me for Leetcode link): There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties:
- There are no self-edges (graph[u] does not contain u).
- There are no parallel edges (graph[u] does not contain duplicate values).
- If v is in graph[u], then u is in graph[v] (the graph is undirected).
- The graph may not be connected, meaning there may be two nodes u and v such that there is no path between them.
A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.
Return true if and only if it is bipartite.
Explanation:
A bipartite graph is a graph where nodes can be separated into two distinct sets, ensuring that neighboring nodes have different colors.
Linear graphs are inherently bipartite, and graphs with even cycles are always guaranteed to be bipartite.
Steps:
- Create a visited array which can store different value.
-1 for unvisited.
0 for first colour.
1 for second colour. - Do DFS traversal on graph for ever unvisited node we will inititate a dfs with initial color as 0.
- At any moment if we get a node which is already coloured with the same colour of current node we will return false.
class Solution {
public:
bool dfs(vector<vector<int>>& graph, int node, int col, vector<int>& color) {
color[node] = col;
for(auto a:graph[node]) {
if (color[a] != -1 && color[a] == col) {
return false;
}
if(color[a] == -1 && dfs(graph, a, !col, color) == false) {
return false;
}
}
return true;
}
bool isBipartite(vector<vector<int>>& graph) {
int n = graph.size();
vector<int>color(n,-1);
for(int i=0; i<n; i++) {
if(color[i] == -1 && dfs(graph, i, 0, color)==false) {
return false;
}
}
return true;
}
};