"Mastering Graph Algorithms: A Comprehensive DSA Graph Common Question Patterns CheatSheet"
11596
"Mastering Graph Algorithms: A Comprehensive DSA Graph Common Question Patterns CheatSheet"
Are you struggling to tackle graph-related coding challenges in your data structure and algorithms (DSA) journey? Graph-based questions can be quite challenging due to their complex nature, but fear not! In this post, we present to you the ultimate Graph Common Question Patterns CheatSheet that will equip you with the tools to conquer any graph problem that comes your way. With this CheatSheet, you'll have a structured approach to tackle various graph problems efficiently.
Disclaimer: The code snippets used in this post are written in
Java. However, you can rewrite or adapt them to any programming language of your choice. The logic and algorithms remain the same regardless of the language used. Happy coding!
Graph Representation
Before diving into the patterns, let's briefly touch upon the two most common ways to represent a graph:
- Adjacency Matrix: A 2D array where
matrix[i][j]represents the weight of the edge between nodesiandj. For an unweighted graph, you can use a boolean matrix, wherematrix[i][j]istrueif there is an edge andfalseotherwise. - Adjacency List: A collection of lists or arrays where the
i-thlist contains all the neighbors of nodeiI usedHashMapfor Adjacency List withkeysas Nodes andArrayListsas ****neighbors.
Choose the representation that best suits your problem and familiarity with the graph.
Graph class
public class Graph<T> {
private final HashMap<T, List<T>> adjList;
private final boolean bidirection;
public HashMap<T, List<T>> getAdjList() {
return adjList;
}
public Graph(boolean bidirection) {
adjList = new HashMap<>();
this.bidirection = bidirection;
}
public void addVertex(T v){
adjList.put(v, new ArrayList<T>());
}
public void addEdge(T source, T destination){
if(!adjList.containsKey(source))
addVertex(source);
if (!adjList.containsKey(destination))
addVertex(destination);
adjList.get(source).add(destination);
if (bidirection)
adjList.get(destination).add(source);
}Graph Traversal
Depth-First Search (DFS)
/* DFS Iterative Method
-------------------------------------------------------------------------------------*/
private static void dfs(Graph<String> graph, String source ){
Stack<String> stack = new Stack<>();
stack.push(source);
while(!stack.empty()){
String curr = stack.pop();
System.out.println(curr);
for (String neighbour: graph.getAdjList().get(curr)){
stack.push(neighbour);
}
}
}
/*-----------------------------------------------------------------------------------*/
/* DFS Recursive Method
-------------------------------------------------------------------------------------*/
private static void dfs(Graph<String> graph, String source ){
System.out.println(source);
for (String neighbour: graph.getAdjList().get(source)){
dfs(graph, neighbour);
}
}
/*-----------------------------------------------------------------------------------*/Breadth-First Search (BFS)
/* BFS Method
-------------------------------------------------------------------------------------*/
private static void bfs(Graph<String> graph, String source ){
Queue<String> queue = new LinkedList<>();
queue.add(source);
int level = 0;
while (!queue.isEmpty()){
int sz = queue.size(); // level size
for(int i = 0; i < sz; i++){
String curr = queue.poll();
System.out.println(curr);
for (String neighbour: graph.getAdjList().get(curr))
queue.add(neighbour);
}
level++;
}
}
/*-----------------------------------------------------------------------------------*/
Traversal Pattern Questions
Number of Connected Components
/* Number of Connected Components
----------------------------------------------------------------------------------------------------------*/
public static int ConnectedComponents(Graph<Integer> graph){
HashSet<Integer> visited = new HashSet<>();
int count = 0;
for (int node: graph.getAdjList().keySet()){
if(explore(graph, node, visited))
count++;
}
return count;
}
private static boolean explore(Graph<Integer> graph, int current, HashSet<Integer> visited) {
if (visited.contains(current))
return false;
visited.add(current);
for (int neighbour: graph.getAdjList().get(current)){
explore(graph, neighbour, visited);
}
return true;
}
/*--------------------------------------------------------------------------------------------------------*/Detect cycle in an undirected graph
/* Detect cycle in an undirected graph
---------------------------------------------------------------------------------------------------------------*/
public boolean isCycle(int V, ArrayList<ArrayList<Integer>> adj) {
HashSet<Integer> visited = new HashSet<>();
for (int i = 0; i < V; i++) {
if (!visited.contains(i)){
if (dfs(adj, i, -1, visited))
return true;
}
}
return false;
}
private boolean dfs(ArrayList<ArrayList<Integer>> adj, int src, int parent, HashSet<Integer> visited)
{
visited.add(src);
for (int neighbour : adj.get(src)){
if (!visited.contains(neighbour)) {
if (dfs(adj, neighbour, src, visited))
return true;
} else if (parent != neighbour) {
return true;
}
}
return false;
}
/*-------------------------------------------------------------------------------------------------------------*/Detect cycle in Directed graph
/* Detect cycle in Directed graph
----------------------------------------------------------------------------------------------------------------*/
public boolean isCyclic(int V, ArrayList<ArrayList<Integer>> adj) {
boolean[] visited = new boolean[V];
boolean[] recstack = new boolean[V];
for (int i = 0; i < V; i++){
if (dfs(adj, i, visited, recstack))
return true;
}
return false;
}
private boolean dfs(ArrayList<ArrayList<Integer>> adj, int src, boolean[] visited, boolean[] recstack) {
if (recstack[src])
return true;
if (visited[src])
return false;
visited[src] = true;
recstack[src] = true;
for (int neighbour : adj.get(src)){
if (dfs(adj, neighbour, visited, recstack))
return true;
}
recstack[src] = false;
return false;
}
/*--------------------------------------------------------------------------------------------------------------*/Topological Sort
/* Topological Sort (DFS)
--------------------------------------------------------------------------------------*/
HashSet<Integer> visited;
int index;
public int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj)
{
visited = new HashSet<>();
int[] res = new int[V];
index = V-1;
for(int i = 0; i < adj.size(); i++){
dfs(adj, i, res);
}
return res;
}
private void dfs(ArrayList<ArrayList<Integer>> adj, int src, int[] res){
if(visited.contains(src))
return;
visited.add(src);
for(int i : adj.get(src)){
dfs(adj, i, res);
}
res[index--] = src;
}
/*------------------------------------------------------------------------------------*/Topological Sort (Kahn's Algorithm)
/* Topological sort (BFS) (Kahn's Algorithm)
-------------------------------------------------------------------------------------*/
public int[] topoSort(int V, ArrayList<ArrayList<Integer>> adj) {
int[] res = new int[V];
int index = 0;
int[] indeg = new int[V];
for (int i = 0; i < V; i++) {
for (int j : adj.get(i)){
indeg[j]++;
}
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (indeg[i] == 0)
queue.add(i);
}
while (!queue.isEmpty()){
int curr = queue.poll();
res[index++] = curr;
for (int neighbour : adj.get(curr)){
indeg[neighbour]--;
if (indeg[neighbour] == 0)
queue.add(neighbour);
}
}
return res;
}
/*-----------------------------------------------------------------------------------*/Grid Pattern
/* Number of island (DFS)
-------------------------------------------------------------------------------------------------*/
public static int islandCount(char[][] grid){
HashSet<String> visited = new HashSet<>();
int count = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if(explore(grid, r, c, visited))
count++;
}
}
return count;
}
private static boolean explore(char[][] grid, int r, int c, HashSet<String> visited) {
boolean rowInbounds = 0 <= r && r < grid.length;
boolean colInbounds = 0 <= c && c < grid[0].length;
if (!rowInbounds || !colInbounds)
return false;
if (grid[r][c] == 'W') // 'W' Means Water and 'L' Means Land
return false;
String pos = r + "," + c;
if (visited.contains(pos))
return false;
visited.add(pos);
explore(grid, r - 1, c, visited);
explore(grid, r + 1, c, visited);
explore(grid, r, c - 1, visited);
explore(grid, r, c + 1, visited);
return true;
}
/*-------------------------------------------------------------------------------------------------*/💡 Practice Question : No of Islands , Rotting Oranges
/* Rotting Oranges (BFS)
-------------------------------------------------------------------------------------*/
public int orangesRotting(int[][] grid) {
Queue<int[]> queue = new LinkedList<>();
int fresh = 0;
int time = 0;
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 2)
queue.add(new int[]{r,c});
if (grid[r][c] == 1)
fresh++;
}
}
int[][] direction = {{0,1},{0,-1},{1,0},{-1,0}};
while (!queue.isEmpty() && fresh > 0){
int sz = queue.size();
for (int i = 0; i < sz; i++) {
int[] rotten = queue.poll();
int row = rotten[0], col = rotten[1];
for (int[] drc : direction){
int r = drc[0] + row, c = drc[1] + col;
boolean rowbound = 0 <= r && r < grid.length;
boolean colbound = 0 <= c && c < grid[0].length;
if (rowbound && colbound && grid[r][c] == 1){
grid[r][c] = 2;
queue.add(new int[]{r,c});
fresh--;
}
}
}
time++;
}
if(fresh == 0)
return time;
return -1;
}📝Note : Look closely DFS & BFS are the two approaches discussed above. How I Use the BFS Method to Traverse the Grid Using a direction array This will be applied to a variety of questions.
Shortest Path
💡 Practice Question : find the city with the smallest number of neighbors at a threshold distance
checkout its editorial for better understanding of all shortest path alogorithms .
BFS
/* Shortest Path (src -> dest) (BFS)
--------------------------------------------------------------------------------------*/
public static int shortestPath(Graph<Integer> graph, int src, int dest){
HashSet<Integer> visited = new HashSet<>();
Queue<Pairs<Integer, Integer>> queue = new LinkedList<>();
visited.add(src);
queue.add(new Pairs<>(src,0));
while (queue.size() > 0){
Pairs<Integer, Integer> curr = queue.poll();
int node = curr.getFirst();
int distance = curr.getSecond();
if (node == dest)
return distance;
for (int neighbour : graph.getAdjList().get(node)){
if (!visited.contains(neighbour)){
visited.add(neighbour);
queue.add(new Pairs<>(neighbour, distance + 1));
}
}
}
return -1;
}
/*-----------------------------------------------------------------------------------*/Shortest Path in weighted DAG
/* Topological Sort Method - O(V+E)
----------------------------------------------------------------------------------------------------------------------------------------------------*/
public static Integer[] shortestPath(int N,int M, int[][] edges, int source) {
HashMap<Integer, List<Pairs<Integer, Integer>>> graph;
graph = buildGraph(edges, N);
int[] toposort = new int[N];
int[] index = {N-1};
HashSet<Integer> visited = new HashSet<>();
for (int i = 0; i < N; i++) {
toposort(graph, i, visited, toposort, index);
}
Integer[] dist = new Integer[N];
dist[source] = 0;
for (int i = 0; i < N; i++) {
int node = toposort[i];
if (dist[node] != null && graph.get(node) != null){
for (Pairs<Integer, Integer> neighbour : graph.get(node)){
int newdist = dist[node] + neighbour.getSecond();
if (dist[neighbour.getFirst()] == null)
dist[neighbour.getFirst()] = newdist;
else
dist[neighbour.getFirst()] = Math.min(dist[neighbour.getFirst()], newdist);
}
}
}
return dist;
}
private static HashMap<Integer, List<Pairs<Integer, Integer>>> buildGraph(int[][] edges, int V){
HashMap<Integer, List<Pairs<Integer, Integer>>> graph = new HashMap<>();
for (int i=0; i<V; i++){
graph.put(i, new ArrayList<>());
}
for (int[] edge : edges){
int a = edge[0], b = edge[1], w = edge[2];
graph.get(a).add(new Pairs<>(b, w));
}
return graph;
}
private static void toposort(HashMap<Integer, List<Pairs<Integer, Integer>>> graph, int src, HashSet<Integer> visited, int[] res, int[] i){
if (visited.contains(src))
return;
visited.add(src);
for (Pairs<Integer, Integer> ne : graph.get(src)){
toposort(graph, ne.getFirst(), visited, res, i);
}
res[i[0]--] = src;
}
/*---------------------------------------------------------------------------------------------------------------------------------------------------*/Dijkstra's Algorithm
/* Dijkstra's Algorithm
--------------------------------------------------------------------------------------------------------------------*/
public int[] Dijkstra(HashMap<Integer, List<Pairs<Integer, Integer>>> graph, int src, int N){
int[] dist = new int[N];
Arrays.fill(dist, Integer.MAX_VALUE);
PriorityQueue<Pairs<Integer, Integer>> q = new PriorityQueue<>((x,y) -> x.second - y.second);
q.add(new Pairs<>(src, 0));
dist[src] = 0;
while (!q.isEmpty()){
Pairs<Integer, Integer> curr = q.poll();
int currNode = curr.first;
int distance = curr.second;
if (dist[currNode] < distance)
continue;
for (Pairs<Integer, Integer> neighbour : graph.get(currNode)){
int new_distance = dist[currNode] + neighbour.second;
if (new_distance < dist[neighbour.first]){
dist[neighbour.first] = new_distance;
q.add(new Pairs<>(neighbour.first, new_distance));
}
}
}
return dist;
}
/*------------------------------------------------------------------------------------------------------------------*/
class Pairs<T1, T2> {
T1 first;
T2 second;
public Pairs(T1 first, T2 second) {
this.first = first;
this.second = second;
}
}Bellman-Ford Algorithm
/* Bellman-Ford Algorithm
--------------------------------------------------------------------------------------*/
public int[] bellman_ford(int V, ArrayList<ArrayList<Integer>> edges, int src) {
int[] dist = new int[V];
Arrays.fill(dist, (int)1e8);
dist[src] = 0;
for(int i=0; i<V-1; i++){
for(ArrayList<Integer> edge : edges){
int u = edge.get(0);
int v = edge.get(1);
int c = edge.get(2);
if(dist[u] != 1e8 && dist[u] + c < dist[v]){
dist[v] = dist[u] + c;
}
}
}
// Check for any cycle present
for(ArrayList<Integer> edge : edges){
int u = edge.get(0);
int v = edge.get(1);
int c = edge.get(2);
if(dist[u] != 1e8 && dist[u] + c < dist[v]){
return new int[]{-1};
}
}
return dist;
}
/*------------------------------------------------------------------------------------*/Floyd Warshall Algorithm
/* Floyd Warshall Algorithm
--------------------------------------------------------------------------------------*/
public void shortest_distance(int[][] matrix) {
int INF = (int)1e9;
int n = matrix.length;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == -1)
matrix[i][j] = INF;
if (i == j)
matrix[i][j] = 0;
}
}
for (int k = 0; k < n; ++k) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i][k] + matrix[k][j]);
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(matrix[i][j] == INF)
matrix[i][j] = -1;
}
}
}
/*------------------------------------------------------------------------------------*/Union-Find Data Structure
/* Union Find Data Structure
------------------------------------------------------------------------------------*/
static class DSU {
int[] parent;
int[] rank;
int[] size;
public DSU(int sz) {
rank = new int[sz];
size = new int[sz];
parent = new int[sz];
for (int i = 0; i < sz; i++){
parent[i] = i;
size[i] = 1;
}
}
public int find(int x) {
if (parent[x] != x)
parent[x] = find(parent[x]);
return parent[x];
}
// Union By Rank
public boolean union_rank(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) {
return false;
} else if (rank[xr] < rank[yr]) {
parent[xr] = yr;
} else if (rank[xr] > rank[yr]) {
parent[yr] = xr;
} else {
parent[yr] = xr;
rank[xr]++;
}
return true;
}
// Union By Size
public boolean union_size(int x, int y) {
int xr = find(x), yr = find(y);
if (xr == yr) {
return false;
} else if (size[xr] < size[yr]) {
parent[xr] = yr;
size[yr] += size[xr];
}
else {
parent[yr] = xr;
size[xr] += size[yr];
}
return true;
}
}
/*----------------------------------------------------------------------------------*/Minimum Spanning Tree
Prim's Algorithm
/* MST Prim's Algorithm
-------------------------------------------------------------------------------------------*/
private int prim(Map<Integer, List<int[]>> graph, int V){
boolean[] visited = new boolean[V];
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
// select any vertex as start let say 0
pq.add(new int[]{0, 0});
int totalCost = 0;
while(!pq.isEmpty()){
int sz = pq.size();
for(int i = 0; i < sz; i++){
int[] crr = pq.poll();
int v = crr[0];
int c = crr[1];
if(visited[v])
continue;
totalCost += c;
visited[v] = true;
for(int[] ne: graph.get(v)){
if(!visited[ne[0]])
pq.add(ne);
}
}
}
return totalCost;
}
/*-----------------------------------------------------------------------------------------*/Kruskal's Algorithm
/* MST Kruskal's Algorithm
------------------------------------------------------------------------------------------------*/
public int spanningTree(int V, int E, int[][] edges){
Arrays.sort(edges, (x, y) -> x[2] - y[2]);
int ans = 0;
DSU dsu = new DSU(V);
// for optimization add only V-1 edges to ans.
for(int i = 0; i < E; i++){
if(dsu.union_rank(edges[i][0], edges[i][1]))
ans += edges[i][2];
}
return ans;
}
/*-----------------------------------------------------------------------------------------------*/Kosaraju's Algorithm
Number of Strongly Connected Components
/* No of Strongly Connected Components (Kosaraju's Algorithm)
------------------------------------------------------------------------------------------------------------------*/
public int kosaraju(int V, ArrayList<ArrayList<Integer>> adj)
{
boolean[] visited = new boolean[V];
Stack<Integer> stack = new Stack<>(); // this will store nodes order Sorted by finish time.
for (int i = 0; i < V; i++) {
if (!visited[i])
dfs(i, adj, visited, stack); // This dfs if for finding sorted order.
}
ArrayList<ArrayList<Integer>> adjT = new ArrayList<>(); // reverse edges Graph.
for (int i = 0; i < V; i++) {
adjT.add(new ArrayList<>());
visited[i] = false;
}
for (int i = 0; i < V; i++) {
for (int ne : adj.get(i)){
adjT.get(ne).add(i);
}
}
int res = 0; // store no of SCC's.
while (!stack.empty()){
int curr = stack.pop();
if (!visited[curr]) {
dfsT(curr, adjT, visited);
res++;
}
}
return res;
}
private void dfs(int node, ArrayList<ArrayList<Integer>> adj, boolean[] visited, Stack<Integer> stack) {
visited[node] = true;
for (int ne : adj.get(node)){
if (!visited[ne])
dfs(ne, adj, visited, stack);
}
stack.push(node);
}
private void dfsT(int node, ArrayList<ArrayList<Integer>> adj, boolean[] visited) {
visited[node] = true;
for (int ne : adj.get(node)){
if (!visited[ne])
dfsT(ne, adj, visited);
}
}
/*----------------------------------------------------------------------------------------------------------------*/Conclusion
Unleash your coding prowess with this DSA Graph Common Question Patterns CheatSheet! From traversing graphs to finding shortest paths and solving connectivity challenges, this CheatSheet has got you covered.
Mastering graph algorithms has never been easier. With this powerful CheatSheet at your disposal, you can confidently conquer any graph problem that comes your way.
Don't keep this gem to yourself! 👍Like, ⬆️upvote, and share this CheatSheet with your friends and fellow coders, and let's level up together in the world of graphs!
Happy coding and let's make graph problems a piece of cake! 🚀📈👍
Comments (12)