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.
| Representations | Adjacency list, adjacency matrix, edge list |
|---|---|
| Traversal cost | O(V + E) with an adjacency list |
| Directed vs undirected | Cycle detection differs |
| Languages | Python 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
- Treating an undirected edge as a single directed edge when building the adjacency list.
- Marking nodes visited when popping instead of when pushing, which lets a node enter the queue many times.
- Using a plain visited flag for directed cycle detection instead of three states.
- Assuming vertices are labelled from 0 when the input is 1-indexed.
- Overflowing when adding infinities in shortest-path code.
Graph Interview Questions and Answers: questions with worked answers
1 Find the town judge using degrees
easyThe 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.
pythondef 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 -1javaint 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 Does a path exist between two vertices?
easyBuild 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).
pythonfrom 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 Falsejavaboolean 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 Count connected components in an undirected graph
mediumRun 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.
pythondef 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 compsjavaint 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 Clone a connected undirected graph
mediumCopy 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.
pythondef 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]javaNode 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 Is the graph bipartite?
mediumColour 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.
pythonfrom 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 Truejavaboolean 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 Detect a cycle in an undirected graph
mediumRun 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.
pythondef 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))javaboolean 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 Detect a cycle in a directed graph
mediumUse 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.
pythondef 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))javaboolean 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 Is a set of edges a valid tree?
mediumA 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).
pythondef 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) == njavaboolean 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 Find all paths from source to target in a DAG
mediumBacktrack: 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.
pythondef 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 resjavaList<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 All-pairs shortest paths with Floyd-Warshall
hardKeep 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.
pythondef 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 djavalong[][] 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 Critical connections (bridges) in a network
hardAn 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.
pythondef 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 resjavaint 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
- Greedy algorithm interview questions with worked solutions
- Grid and Matrix DP Interview Questions
- Hashing interview questions with worked solutions
- Heap and Priority Queue Interview Questions
- Interval DP Interview Questions
- Interval interview questions with worked solutions
- Kadane algorithm interview questions with worked solutions
- KMP and string matching interview questions with solutions
- Knapsack DP Interview Questions
- Linked list interview questions with worked solutions
- Longest Common Subsequence (LCS) Interview Questions
- Longest Increasing Subsequence (LIS) Interview Questions