Autocoder

Graph Interview Questions and Answers

Last updated 2026-11-19

Graphs model networks, dependencies and maps, and interview questions on them test whether you pick the right representation and traversal. The problems below cover the core ideas: connectivity, cycles, colouring, copying and all-pairs distances, each with Python and Java code.

Specific algorithms have their own pages: BFS, DFS, topological sort, Dijkstra and union-find. This page focuses on modelling and the questions that sit between them.

RepresentationsAdjacency list, adjacency matrix, edge list
Traversal costO(V + E) with an adjacency list
Directed vs undirectedCycle detection differs
LanguagesPython and Java

The pattern and when to spot it

First decide how to read the input. An edge list usually becomes an adjacency list, sized V plus E; a dense graph with small V can use a matrix, but a matrix makes traversal O(V^2). Check whether the graph is directed, weighted and whether it can be disconnected. Disconnected input is the most common hidden trap: always loop over every vertex as a possible start.

Then match the question to a tool. Reachability and components need any traversal. Fewest edges needs BFS. Ordering with dependencies needs topological sort. Cheapest paths with weights need Dijkstra, or Bellman-Ford with negative edges. Connecting everything cheaply needs a minimum spanning tree. If a problem sounds like a graph but nothing is stated, look for entities that depend on or reach each other.

Frequent mistakes

Graph Interview Questions and Answers: questions with worked answers

  1. 1

    Find the town judge using degrees

    easy

    The judge trusts nobody and is trusted by the other n-1 people. Keep one counter per person: add 1 when someone is trusted, subtract 1 when they trust someone. The judge ends with exactly n-1. No adjacency list is needed. Time O(n + E), space O(n). Edge cases: n equal to 1 with no trust edges (judge is person 1), two people who both look like candidates, a person trusted by everyone who also trusts someone.

    python
    def find_judge(n, trust):
        score = [0] * (n + 1)
        for a, b in trust:
            score[a] -= 1
            score[b] += 1
        for i in range(1, n + 1):
            if score[i] == n - 1:
                return i
        return -1
    java
    int findJudge(int n, int[][] trust) {
        int[] score = new int[n + 1];
        for (int[] t : trust) { score[t[0]]--; score[t[1]]++; }
        for (int i = 1; i <= n; i++) if (score[i] == n - 1) return i;
        return -1;
    }
  2. 2

    Does a path exist between two vertices?

    easy

    Build an adjacency list from the edge list, then run a DFS or BFS from the source with a visited set and stop when you reach the destination. Mark nodes visited when you push them so each is processed once. Time O(V + E), space O(V + E). Edge cases: source equal to destination (true), isolated vertices, edges listed in one direction only when the graph is undirected (add both).

    python
    from collections import defaultdict, deque
    def valid_path(n, edges, src, dst):
        g = defaultdict(list)
        for a, b in edges:
            g[a].append(b); g[b].append(a)
        seen, dq = {src}, deque([src])
        while dq:
            u = dq.popleft()
            if u == dst:
                return True
            for v in g[u]:
                if v not in seen:
                    seen.add(v); dq.append(v)
        return False
    java
    boolean validPath(int n, int[][] edges, int src, int dst) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        Deque<Integer> q = new ArrayDeque<>();
        q.add(src); seen[src] = true;
        while (!q.isEmpty()) {
            int u = q.poll();
            if (u == dst) return true;
            for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; q.add(v); }
        }
        return false;
    }
  3. 3

    Count connected components in an undirected graph

    medium

    Run a traversal from every unvisited vertex and increment a counter each time you start a new one. Every vertex is visited once overall. Union-find is an equally good answer, see union-find interview questions. Time O(V + E), space O(V + E). Edge cases: no edges (every vertex is its own component), n equal to 0, self-loops and parallel edges, which do not change the count.

    python
    def count_components(n, edges):
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b); g[b].append(a)
        seen, comps = [False] * n, 0
        for s in range(n):
            if seen[s]:
                continue
            comps += 1
            seen[s] = True
            stack = [s]
            while stack:
                u = stack.pop()
                for v in g[u]:
                    if not seen[v]:
                        seen[v] = True
                        stack.append(v)
        return comps
    java
    int countComponents(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        int comps = 0;
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            comps++;
            Deque<Integer> st = new ArrayDeque<>();
            st.push(s); seen[s] = true;
            while (!st.isEmpty()) {
                int u = st.pop();
                for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; st.push(v); }
            }
        }
        return comps;
    }
  4. 4

    Clone a connected undirected graph

    medium

    Copy each node once and keep a map from original to clone. When visiting a node, create its clone if absent, then for each neighbour create or fetch its clone and add it to the clone adjacency list. The map also breaks cycles. Time O(V + E), space O(V). Edge cases: null input returns null, a single node with no neighbours, self-loop, cycles that would otherwise recurse forever.

    python
    def clone_graph(node):
        if not node:
            return None
        copies = {node: Node(node.val)}
        stack = [node]
        while stack:
            u = stack.pop()
            for v in u.neighbors:
                if v not in copies:
                    copies[v] = Node(v.val)
                    stack.append(v)
                copies[u].neighbors.append(copies[v])
        return copies[node]
    java
    Node cloneGraph(Node node) {
        if (node == null) return null;
        Map<Node, Node> copies = new HashMap<>();
        copies.put(node, new Node(node.val, new ArrayList<>()));
        Deque<Node> st = new ArrayDeque<>();
        st.push(node);
        while (!st.isEmpty()) {
            Node u = st.pop();
            for (Node v : u.neighbors) {
                if (!copies.containsKey(v)) {
                    copies.put(v, new Node(v.val, new ArrayList<>()));
                    st.push(v);
                }
                copies.get(u).neighbors.add(copies.get(v));
            }
        }
        return copies.get(node);
    }
  5. 5

    Is the graph bipartite?

    medium

    Colour vertices with two colours so every edge joins different colours. BFS from each uncoloured vertex, give neighbours the opposite colour, and fail if an edge joins two equal colours. Equivalently, the graph is bipartite exactly when it has no odd cycle. Time O(V + E), space O(V). Edge cases: disconnected graphs (start a search from every uncoloured vertex), self-loop (never bipartite), empty graph.

    python
    from collections import deque
    def is_bipartite(graph):
        color = {}
        for s in range(len(graph)):
            if s in color:
                continue
            color[s] = 0
            dq = deque([s])
            while dq:
                u = dq.popleft()
                for v in graph[u]:
                    if v not in color:
                        color[v] = 1 - color[u]
                        dq.append(v)
                    elif color[v] == color[u]:
                        return False
        return True
    java
    boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1);
        for (int s = 0; s < n; s++) {
            if (color[s] != -1) continue;
            color[s] = 0;
            Deque<Integer> q = new ArrayDeque<>();
            q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : graph[u]) {
                    if (color[v] == -1) { color[v] = 1 - color[u]; q.add(v); }
                    else if (color[v] == color[u]) return false;
                }
            }
        }
        return true;
    }
  6. 6

    Detect a cycle in an undirected graph

    medium

    Run DFS and carry the parent. If you reach an already visited vertex that is not the parent, there is a cycle. Skipping only the single edge back to the parent matters when parallel edges can exist; in that case compare edge ids rather than vertices. Time O(V + E), space O(V). Edge cases: disconnected graphs, a single edge (no cycle, since the visited neighbour is the parent), self-loop, deep graphs where recursion overflows.

    python
    def has_cycle_undirected(n, edges):
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b); g[b].append(a)
        seen = [False] * n
        def dfs(u, parent):
            seen[u] = True
            for v in g[u]:
                if not seen[v]:
                    if dfs(v, u):
                        return True
                elif v != parent:
                    return True
            return False
        return any(not seen[s] and dfs(s, -1) for s in range(n))
    java
    boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        for (int s = 0; s < n; s++)
            if (!seen[s] && dfs(g, s, -1, seen)) return true;
        return false;
    }
    private boolean dfs(List<List<Integer>> g, int u, int parent, boolean[] seen) {
        seen[u] = true;
        for (int v : g.get(u)) {
            if (!seen[v]) { if (dfs(g, v, u, seen)) return true; }
            else if (v != parent) return true;
        }
        return false;
    }
  7. 7

    Detect a cycle in a directed graph

    medium

    Use three states: unvisited, on the current DFS path, and finished. Reaching a vertex that is on the current path is a back edge, so there is a cycle. A visited-only flag is wrong because a finished vertex can be reached again without forming a cycle. Time O(V + E), space O(V). Edge cases: self-loop, two paths converging on one vertex (a diamond, which is not a cycle), disconnected components.

    python
    def has_cycle_directed(n, edges):
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b)
        state = [0] * n  # 0 new, 1 on path, 2 done
        def dfs(u):
            state[u] = 1
            for v in g[u]:
                if state[v] == 1 or (state[v] == 0 and dfs(v)):
                    return True
            state[u] = 2
            return False
        return any(state[s] == 0 and dfs(s) for s in range(n))
    java
    boolean hasCycle(int n, int[][] edges) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) g.get(e[0]).add(e[1]);
        int[] state = new int[n];
        for (int s = 0; s < n; s++)
            if (state[s] == 0 && dfs(g, s, state)) return true;
        return false;
    }
    private boolean dfs(List<List<Integer>> g, int u, int[] state) {
        state[u] = 1;
        for (int v : g.get(u)) {
            if (state[v] == 1) return true;
            if (state[v] == 0 && dfs(g, v, state)) return true;
        }
        state[u] = 2;
        return false;
    }
  8. 8

    Is a set of edges a valid tree?

    medium

    A graph is a tree when it is connected and has exactly n-1 edges. Check the edge count first, then confirm one traversal from vertex 0 reaches all n vertices. With n-1 edges, connectivity alone rules out cycles. Time O(V + E), space O(V + E). Edge cases: n equal to 1 with no edges (a tree), n-1 edges but disconnected with a cycle elsewhere, more than n-1 edges (fail immediately).

    python
    def valid_tree(n, edges):
        if len(edges) != n - 1:
            return False
        g = [[] for _ in range(n)]
        for a, b in edges:
            g[a].append(b); g[b].append(a)
        seen, stack = {0}, [0]
        while stack:
            u = stack.pop()
            for v in g[u]:
                if v not in seen:
                    seen.add(v); stack.append(v)
        return len(seen) == n
    java
    boolean validTree(int n, int[][] edges) {
        if (edges.length != n - 1) return false;
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (int[] e : edges) { g.get(e[0]).add(e[1]); g.get(e[1]).add(e[0]); }
        boolean[] seen = new boolean[n];
        Deque<Integer> st = new ArrayDeque<>();
        st.push(0); seen[0] = true;
        int cnt = 1;
        while (!st.isEmpty()) {
            int u = st.pop();
            for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; cnt++; st.push(v); }
        }
        return cnt == n;
    }
  9. 9

    Find all paths from source to target in a DAG

    medium

    Backtrack: add the current vertex to the path, recurse into every neighbour, record the path on reaching the target and remove the vertex when returning. The graph is acyclic, so no visited set is needed. Time O(2^V * V) in the worst case, space O(V) recursion plus output. Edge cases: target equals source, vertices that cannot reach the target, output size itself being exponential.

    python
    def all_paths(graph):
        target, res, path = len(graph) - 1, [], [0]
        def dfs(u):
            if u == target:
                res.append(path[:])
                return
            for v in graph[u]:
                path.append(v)
                dfs(v)
                path.pop()
        dfs(0)
        return res
    java
    List<List<Integer>> allPaths(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> path = new ArrayList<>(List.of(0));
        dfs(graph, 0, path, res);
        return res;
    }
    private void dfs(int[][] g, int u, List<Integer> path, List<List<Integer>> res) {
        if (u == g.length - 1) { res.add(new ArrayList<>(path)); return; }
        for (int v : g[u]) {
            path.add(v);
            dfs(g, v, path, res);
            path.remove(path.size() - 1);
        }
    }
  10. 10

    All-pairs shortest paths with Floyd-Warshall

    hard

    Keep a matrix d[i][j] of best known distances, initially the edge weights, 0 on the diagonal and infinity otherwise. For each intermediate vertex k, try to improve every pair via k. The k loop must be outermost for correctness. A negative d[i][i] afterwards reveals a negative cycle. Time O(V^3), space O(V^2). Edge cases: infinity overflow when adding two infinities (use a large value such as 10^9 in int or a guard), disconnected pairs, negative cycles.

    python
    def floyd_warshall(n, edges):
        INF = float('inf')
        d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
        for u, v, w in edges:
            d[u][v] = min(d[u][v], w)
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    if d[i][k] + d[k][j] < d[i][j]:
                        d[i][j] = d[i][k] + d[k][j]
        return d
    java
    long[][] floydWarshall(int n, int[][] edges) {
        long INF = (long) 1e15;
        long[][] d = new long[n][n];
        for (long[] row : d) Arrays.fill(row, INF);
        for (int i = 0; i < n; i++) d[i][i] = 0;
        for (int[] e : edges) d[e[0]][e[1]] = Math.min(d[e[0]][e[1]], e[2]);
        for (int k = 0; k < n; k++)
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
        return d;
    }
  11. 11

    Critical connections (bridges) in a network

    hard

    An edge is a bridge if removing it disconnects the graph. Run DFS recording discovery time disc[u] and low[u], the earliest discovery time reachable from u using at most one back edge. For a tree edge u to v, if low[v] is greater than disc[u], then v cannot reach above u without that edge, so it is a bridge. This is Tarjan algorithm. Time O(V + E), space O(V + E). Edge cases: graph that is a single tree (every edge is a bridge), a cycle (none), multiple components, skipping the parent edge during the low update, deep recursion.

    python
    def critical_connections(n, connections):
        g = [[] for _ in range(n)]
        for a, b in connections:
            g[a].append(b); g[b].append(a)
        disc, low, t, res = [-1] * n, [0] * n, [0], []
        def dfs(u, parent):
            disc[u] = low[u] = t[0]; t[0] += 1
            for v in g[u]:
                if v == parent:
                    continue
                if disc[v] == -1:
                    dfs(v, u)
                    low[u] = min(low[u], low[v])
                    if low[v] > disc[u]:
                        res.append([u, v])
                else:
                    low[u] = min(low[u], disc[v])
        dfs(0, -1)
        return res
    java
    int timer;
    List<List<Integer>> criticalConnections(int n, List<List<Integer>> conns) {
        List<List<Integer>> g = new ArrayList<>();
        for (int i = 0; i < n; i++) g.add(new ArrayList<>());
        for (List<Integer> c : conns) { g.get(c.get(0)).add(c.get(1)); g.get(c.get(1)).add(c.get(0)); }
        int[] disc = new int[n], low = new int[n];
        Arrays.fill(disc, -1);
        List<List<Integer>> res = new ArrayList<>();
        timer = 0;
        dfs(g, 0, -1, disc, low, res);
        return res;
    }
    private void dfs(List<List<Integer>> g, int u, int parent, int[] disc, int[] low, List<List<Integer>> res) {
        disc[u] = low[u] = timer++;
        for (int v : g.get(u)) {
            if (v == parent) continue;
            if (disc[v] == -1) {
                dfs(g, v, u, disc, low, res);
                low[u] = Math.min(low[u], low[v]);
                if (low[v] > disc[u]) res.add(List.of(u, v));
            } else low[u] = Math.min(low[u], disc[v]);
        }
    }

Frequently asked questions

Should I use an adjacency list or a matrix?

Use an adjacency list for sparse graphs, which is almost every interview problem. A matrix takes O(V^2) memory and makes neighbour scans O(V), but gives O(1) edge lookup for dense graphs.

What is the difference between BFS and DFS?

BFS visits vertices in increasing edge distance using a queue and finds fewest-edge paths. DFS goes deep first using a stack or recursion and suits cycles, components and ordering problems.

How do I detect a cycle in a directed graph?

Use DFS with three states, or Kahn topological sort. If the sort cannot process every vertex, a cycle exists.

Where do graph problems show up in hiring tests?

They appear in coding rounds of product companies and in many online assessments. See how to crack the technical interview for how these rounds are usually run.

Related guides

More in DSA Interview Questions

See all in this section