Top 20 Graph Algorithm Interview Questions and Answers (2026)

1. Why Graphs Are Critical for Interviews

Graphs are the most versatile data structure in computer science. Real-world problems in navigation (Google Maps), social networks (LinkedIn/Facebook), dependency management, and network routing all map directly to graph algorithms.

Below are top Graph interview questions with detailed explanations, intuition, and implementations in C++, Java, Python, and JavaScript.

2. Graph Representation & Basics

Adjacency list is the standard graph representation:

cpp
#include <vector>
using namespace std;
vector<vector<int>> adj(n); // Adjacency list

java
import java.util.*;
List<List<Integer>> adj = new ArrayList<>();

python
from collections import defaultdict
adj = defaultdict(list)

javascript
const adj = new Map();

3. Easy & Medium Graph Questions

Q1. Number of Islands (Grid BFS/DFS)

Question: Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

cpp
void dfs(vector<vector<char>>& grid, int r, int c) {
    int m = grid.size(), n = grid[0].size();
    if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == '0') return;
    grid[r][c] = '0';
    dfs(grid, r+1, c); dfs(grid, r-1, c);
    dfs(grid, r, c+1); dfs(grid, r, c-1);
}
int numIslands(vector<vector<char>>& grid) {
    int count = 0;
    for (int i = 0; i < grid.size(); i++) {
        for (int j = 0; j < grid[0].size(); j++) {
            if (grid[i][j] == '1') {
                count++;
                dfs(grid, i, j);
            }
        }
    }
    return count;
}

java
public class Solution {
    private void dfs(char[][] grid, int r, int c) {
        int m = grid.length, n = grid[0].length;
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] == '0') return;
        grid[r][c] = '0';
        dfs(grid, r + 1, c); dfs(grid, r - 1, c);
        dfs(grid, r, c + 1); dfs(grid, r, c - 1);
    }
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    count++;
                    dfs(grid, i, j);
                }
            }
        }
        return count;
    }
}

python
def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] == '0':
            return
        grid[r][c] = '0'
        dfs(r + 1, c); dfs(r - 1, c)
        dfs(r, c + 1); dfs(r, c - 1)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                count += 1
                dfs(i, j)
    return count

javascript
function numIslands(grid) {
    if (!grid || grid.length === 0) return 0;
    let m = grid.length, n = grid[0].length;
    let count = 0;

    function dfs(r, c) {
        if (r < 0 || r >= m || c < 0 || c >= n || grid[r][c] === '0') return;
        grid[r][c] = '0';
        dfs(r + 1, c); dfs(r - 1, c);
        dfs(r, c + 1); dfs(r, c - 1);
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === '1') {
                count++;
                dfs(i, j);
            }
        }
    }
    return count;
}

Time Complexity: O(m x n) | Space Complexity: O(m x n) call stack

Q2. Clone Graph

Question: Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph.

cpp
#include <unordered_map>
using namespace std;

class Node {
public:
    int val;
    vector<Node*> neighbors;
    Node(int _val) { val = _val; }
};

unordered_map<Node*, Node*> visited;
Node* cloneGraph(Node* node) {
    if (!node) return nullptr;
    if (visited.count(node)) return visited[node];
    Node* clone = new Node(node->val);
    visited[node] = clone;
    for (Node* neighbor : node->neighbors) {
        clone->neighbors.push_back(cloneGraph(neighbor));
    }
    return clone;
}

java
import java.util.*;

class Node {
    public int val;
    public List<Node> neighbors;
    public Node(int _val) { val = _val; neighbors = new ArrayList<>(); }
}

public class Solution {
    private Map<Node, Node> visited = new HashMap<>();
    public Node cloneGraph(Node node) {
        if (node == null) return null;
        if (visited.containsKey(node)) return visited.get(node);
        Node clone = new Node(node.val);
        visited.put(node, clone);
        for (Node neighbor : node.neighbors) {
            clone.neighbors.add(cloneGraph(neighbor));
        }
        return clone;
    }
}

python
class Node:
    def __init__(self, val=0, neighbors=None):
        self.val = val
        self.neighbors = neighbors if neighbors is not None else []

def cloneGraph(node):
    if not node: return None
    visited = {}
    def dfs(curr):
        if curr in visited:
            return visited[curr]
        clone = Node(curr.val)
        visited[curr] = clone
        for neighbor in curr.neighbors:
            clone.neighbors.append(dfs(neighbor))
        return clone
    return dfs(node)

javascript
function cloneGraph(node) {
    if (!node) return null;
    let visited = new Map();

    function dfs(curr) {
        if (visited.has(curr)) return visited.get(curr);
        let clone = { val: curr.val, neighbors: [] };
        visited.set(curr, clone);
        for (let neighbor of curr.neighbors) {
            clone.neighbors.push(dfs(neighbor));
        }
        return clone;
    }
    return dfs(node);
}

Time Complexity: O(V + E) | Space Complexity: O(V)

Q3. Course Schedule (Topological Sort / Cycle Detection)

Question: There are numCourses courses labeled 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [a, b] indicates that you must take course b first. Can you finish all courses?

cpp
bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
    vector<vector<int>> adj(numCourses);
    vector<int> inDegree(numCourses, 0);
    for (auto& p : prerequisites) {
        adj[p[1]].push_back(p[0]);
        inDegree[p[0]]++;
    }
    queue<int> q;
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) q.push(i);
    }
    int count = 0;
    while (!q.empty()) {
        int curr = q.front(); q.pop();
        count++;
        for (int neighbor : adj[curr]) {
            if (--inDegree[neighbor] == 0) q.push(neighbor);
        }
    }
    return count == numCourses;
}

java
public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();
    int[] inDegree = new int[numCourses];
    for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
        inDegree[p[0]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (inDegree[i] == 0) q.add(i);
    }
    int count = 0;
    while (!q.isEmpty()) {
        int curr = q.poll();
        count++;
        for (int neighbor : adj.get(curr)) {
            if (--inDegree[neighbor] == 0) q.add(neighbor);
        }
    }
    return count == numCourses;
}

python
from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    adj = defaultdict(list)
    in_degree = [0] * numCourses
    for dest, src in prerequisites:
        adj[src].append(dest)
        in_degree[dest] += 1

    q = deque([i for i in range(numCourses) if in_degree[i] == 0])
    count = 0
    while q:
        curr = q.popleft()
        count += 1
        for neighbor in adj[curr]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                q.append(neighbor)
    return count == numCourses

javascript
function canFinish(numCourses, prerequisites) {
    let adj = Array.from({ length: numCourses }, () => []);
    let inDegree = new Array(numCourses).fill(0);

    for (let [dest, src] of prerequisites) {
        adj[src].push(dest);
        inDegree[dest]++;
    }

    let q = [];
    for (let i = 0; i < numCourses; i++) {
        if (inDegree[i] === 0) q.push(i);
    }

    let count = 0;
    while (q.length > 0) {
        let curr = q.shift();
        count++;
        for (let neighbor of adj[curr]) {
            inDegree[neighbor]--;
            if (inDegree[neighbor] === 0) q.push(neighbor);
        }
    }
    return count === numCourses;
}

Time Complexity: O(V + E) | Space Complexity: O(V + E)

Q4. Shortest Path in Binary Matrix (BFS)

Question: Given an n x n binary matrix grid, return the length of the shortest clear path from top-left (0,0) to bottom-right (n-1,n-1). Return -1 if no clear path exists.

cpp
int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = grid.size();
    if (grid[0][0] != 0 || grid[n-1][n-1] != 0) return -1;
    queue<pair<int, int>> q;
    q.push({0, 0});
    grid[0][0] = 1;
    int steps = 1;
    int dirs[8][2] = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    while (!q.empty()) {
        int sz = q.size();
        while (sz--) {
            auto [r, c] = q.front(); q.pop();
            if (r == n - 1 && c == n - 1) return steps;
            for (auto& d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                    grid[nr][nc] = 1;
                    q.push({nr, nc});
                }
            }
        }
        steps++;
    }
    return -1;
}

java
public int shortestPathBinaryMatrix(int[][] grid) {
    int n = grid.length;
    if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;
    Queue<int[]> q = new LinkedList<>();
    q.add(new int[]{0, 0});
    grid[0][0] = 1;
    int steps = 1;
    int[][] dirs = {{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}};
    while (!q.isEmpty()) {
        int sz = q.size();
        while (sz-- > 0) {
            int[] curr = q.poll();
            int r = curr[0], c = curr[1];
            if (r == n - 1 && c == n - 1) return steps;
            for (int[] d : dirs) {
                int nr = r + d[0], nc = c + d[1];
                if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] == 0) {
                    grid[nr][nc] = 1;
                    q.add(new int[]{nr, nc});
                }
            }
        }
        steps++;
    }
    return -1;
}

python
from collections import deque

def shortestPathBinaryMatrix(grid: list) -> int:
    n = len(grid)
    if grid[0][0] != 0 or grid[n-1][n-1] != 0:
        return -1
    q = deque([(0, 0, 1)])
    grid[0][0] = 1
    dirs = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
    while q:
        r, c, steps = q.popleft()
        if r == n - 1 and c == n - 1:
            return steps
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < n and 0 <= nc < n and grid[nr][nc] == 0:
                grid[nr][nc] = 1
                q.append((nr, nc, steps + 1))
    return -1

javascript
function shortestPathBinaryMatrix(grid) {
    let n = grid.length;
    if (grid[0][0] !== 0 || grid[n - 1][n - 1] !== 0) return -1;
    let q = [[0, 0, 1]];
    grid[0][0] = 1;
    let dirs = [[-1,-1],[-1,0],[-1,1],[0,-1],[0,1],[1,-1],[1,0],[1,1]];
    while (q.length > 0) {
        let [r, c, steps] = q.shift();
        if (r === n - 1 && c === n - 1) return steps;
        for (let [dr, dc] of dirs) {
            let nr = r + dr, nc = c + dc;
            if (nr >= 0 && nr < n && nc >= 0 && nc < n && grid[nr][nc] === 0) {
                grid[nr][nc] = 1;
                q.push([nr, nc, steps + 1]);
            }
        }
    }
    return -1;
}

Time Complexity: O(n^2) | Space Complexity: O(n^2)

4. Summary Table

Practice all graph problems on DSAMaster's practice platform.