Graph Common Question Patterns CheatSheet
Welcome to ExpertFunda's Ultimate Graph Algorithms Guide!
You will be finding this article most beneficial in learning graph for your faang interview and for leetcode contest.
You will feel it tricky to solve graph-related coding challenges during your data structures and algorithms (DSA) preparation for your next role.
Graph problems are mostly asked in the productbase companies and indeed be complex and daunting at interview times.
No need to worry! At ExpertFunda, we are dedicated to providing you with the most comprehensive guidance on this topic.
If you would like additional assistance with learning graph algorithms, please feel free to reach out to us through the "Contact Us" form. We would be happy to provide further online classes and training to support your learning journey.
We are presenting the ultimate Graph Common Question Patterns CheatSheet — your go-to guide for understanding and efficiently solving graph-based problems.
With this CheatSheet, you'll have a clear and structured approach to tackle a variety of graph challenges with ease.
Disclaimer: The code snippets provided in this guide are written in Java. However, you can easily adapt the logic and algorithms to any programming language of your choice. The concepts remain consistent, no matter which language you use.
Let's Master The Graph Challenges with Confidence!
How can we represent a graph?
The way to store a graph in a computer's memory is called Graph Representation.
Let us guide you through the various methods!
Before diving into the patterns, let's briefly touch upon the two most common ways to represent a graph:
1. Adjacency Matrix: A 2D array where matrix[i][j] represents the weight of the edge between nodes i and j.
For an unweighted graph, you can use a boolean matrix, where matrix[i][j] is true if there is an edge and false otherwise.
How does an adjacency list work in graphs?
This Adjacency matrix of Graph's representation is also known as Sequential representation.
2. Adjacency List: A collection of lists or arrays where the i-th list contains all the neighbors of node i I used HashMap for Adjacency List with keys as Nodes and ArrayLists as neighbors.
Choose the representation that best suits your problem and familiarity with the graph.
How does an adjacency matrix work in graphs?
This Adjacency List of Graph's representation is also known as Linked list representation.
For now, just keep in mind that:-
In sequential representation, an adjacency matrix is used to store the graph. Whereas in linked list representation, there is a use of an adjacency list to store the graph.
We will discuss each one of them in detail later.
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 graph, String source ){
Stack 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 graph, String source ){
System.out.println(source);
for (String neighbour: graph.getAdjList().get(source)){
dfs(graph, neighbour);
}
}
/*-----------------------------------------------------------------------------------*/
Graph Traversal: Breadth-First Search (BFS)
/* BFS Method
-------------------------------------------------------------------------------------*/
private static void bfs(Graph graph, String source ){
Queue 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 graph){
HashSet 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 graph, int current, HashSet visited) {
if (visited.contains(current))
return false;
visited.add(current);
for (int neighbour: graph.getAdjList().get(current)){
explore(graph, neighbour, visited);
}
return true;
}
/*--------------------------------------------------------------------------------------------------------*/
Traversal Pattern Questions: Detect cycle in an undirected graph
/* Detect cycle in an undirected graph
---------------------------------------------------------------------------------------------------------------*/
public boolean isCycle(int V, ArrayList> adj) {
HashSet 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> adj, int src, int parent, HashSet 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;
}
/*-------------------------------------------------------------------------------------------------------------*/
Traversal Pattern Questions: Detect cycle in Directed graph
/* Detect cycle in Directed graph
----------------------------------------------------------------------------------------------------------------*/
public boolean isCyclic(int V, ArrayList> 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> 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 visited;
int index;
public int[] topoSort(int V, ArrayList> 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> 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> 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 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 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 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 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: BFS
Practice Question : find the city with the smallest number of neighbors at a threshold distance
/* Shortest Path (src -> dest) (BFS)
--------------------------------------------------------------------------------------*/
public static int shortestPath(Graph graph, int src, int dest){
HashSet visited = new HashSet<>();
Queue> queue = new LinkedList<>();
visited.add(src);
queue.add(new Pairs<>(src,0));
while (queue.size() > 0){
Pairs 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>> graph;
graph = buildGraph(edges, N);
int[] toposort = new int[N];
int[] index = {N-1};
HashSet 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 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>> buildGraph(int[][] edges, int V){
HashMap>> graph = new HashMap<>();
for (int i=0; i());
}
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>> graph, int src, HashSet visited, int[] res, int[] i){
if (visited.contains(src))
return;
visited.add(src);
for (Pairs ne : graph.get(src)){
toposort(graph, ne.getFirst(), visited, res, i);
}
res[i[0]--] = src;
}
/*---------------------------------------------------------------------------------------------------------------------------------------------------*/
Shortest Path: Dijkstra's Algorithm
/* Dijkstra's Algorithm
--------------------------------------------------------------------------------------------------------------------*/
public int[] Dijkstra(HashMap>> graph, int src, int N){
int[] dist = new int[N];
Arrays.fill(dist, Integer.MAX_VALUE);
PriorityQueue> q = new PriorityQueue<>((x,y) -> x.second - y.second);
q.add(new Pairs<>(src, 0));
dist[src] = 0;
while (!q.isEmpty()){
Pairs curr = q.poll();
int currNode = curr.first;
int distance = curr.second;
if (dist[currNode] < distance)
continue;
for (Pairs 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 first;
T2 second;
public Pairs(T1 first, T2 second) {
this.first = first;
this.second = second;
}
}
Shortest Path: Bellman-Ford Algorithm
/* Bellman-Ford Algorithm
--------------------------------------------------------------------------------------*/
public int[] bellman_ford(int V, ArrayList> edges, int src) {
int[] dist = new int[V];
Arrays.fill(dist, (int)1e8);
dist[src] = 0;
for(int i=0; i 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 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;
}
/*------------------------------------------------------------------------------------*/
Shortest Path: 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> graph, int V){
boolean[] visited = new boolean[V];
PriorityQueue 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;
}
/*-----------------------------------------------------------------------------------------*/
Minimum Spanning Tree: 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;
}
/*-----------------------------------------------------------------------------------------------*/
Minimum Spanning Tree: Kosaraju's Algorithm for Number of Strongly Connected Components
/* No of Strongly Connected Components (Kosaraju's Algorithm)
------------------------------------------------------------------------------------------------------------------*/
public int kosaraju(int V, ArrayList> adj)
{
boolean[] visited = new boolean[V];
Stack 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> 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> adj, boolean[] visited, Stack 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> 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. Let’s level up together in the world of graphs!
Happy coding, and let’s make graph problems a piece of cake!
