Graph Interview Questions

Graph Interview Questions

Graphs are one of the most important data structures in technical interviews because they can model relationships between people, locations, services, dependencies, computers, and many other entities.

Graph interview questions commonly test BFS, DFS, shortest paths, cycle detection, topological sorting, connected components, and minimum spanning trees. The key is often recognizing which graph pattern matches the problem before choosing an algorithm.

1. What Is a Graph Data Structure?

A graph is a non-linear data structure consisting of vertices and edges. Vertices represent entities, while edges represent relationships between them.

A ----- B
|       |
|       |
C ----- D

Graphs can represent networks such as roads between cities, connections between users, links between web pages, or dependencies between software components.

2. What Are the Main Types of Graphs?

• Directed graph: edges have a direction.
• Undirected graph: edges have no direction.
• Weighted graph: edges contain costs or weights.
• Unweighted graph: edges do not have explicit weights.
• Connected graph: vertices are reachable from one another in the relevant sense.
• Disconnected graph: the graph contains multiple disconnected regions.
• Cyclic graph: contains at least one cycle.
• Acyclic graph: contains no cycles.
• DAG: a directed acyclic graph.

3. What Is the Difference Between Directed and Undirected Graphs?

In a directed graph, an edge has a source and destination. In an undirected graph, the relationship works in both directions.

Directed:

A → B

Undirected:

A ↔ B

For example, a social connection may be modeled as undirected, while a one-way road or prerequisite relationship may be modeled as directed.

4. What Is the Difference Between Weighted and Unweighted Graphs?

In a weighted graph, each edge has an associated value such as distance, cost, time, or capacity.

Weighted:

A --5-- B
|       |
2       7
|       |
C --3-- D

Unweighted:

A ----- B
|       |
C ----- D

The distinction is especially important for shortest-path algorithms. BFS works directly for shortest paths measured in edges in an unweighted graph, while weighted graphs may require algorithms such as Dijkstra or Bellman-Ford depending on edge weights.

5. How Can a Graph Be Represented?

The two most common graph representations are the adjacency list and adjacency matrix.

6. What Is an Adjacency List?

An adjacency list stores each vertex together with the vertices directly connected to it.

A → B, C
B → A, D
C → A
D → B

Adjacency lists are particularly useful for sparse graphs because they store only existing edges.

7. What Is an Adjacency Matrix?

An adjacency matrix uses a two-dimensional array where the cell at row i and column j indicates whether an edge exists from vertex i to vertex j.

    A B C
A   0 1 1
B   1 0 0
C   1 0 0

An adjacency matrix requires O(V²) space but provides O(1) edge-existence lookup.

8. What Is BFS in a Graph?

Breadth-First Search (BFS) explores a graph level by level. It normally uses a queue to process vertices in the order in which they are discovered.

        A
       / \
      B   C
     /     \
    D       E

BFS from A:

A → B → C → D → E

9. How Do You Implement BFS?

function bfs(graph, start) {
  const queue = [start];
  const visited = new Set([start]);
  let front = 0;

  while (front < queue.length) {
    const node = queue[front++];

    console.log(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
}

const graph = {
  A: ["B", "C"],
  B: ["D"],
  C: ["E"],
  D: [],
  E: []
};

bfs(graph, "A");

With an adjacency list, BFS takes O(V + E) time because every vertex and edge is processed at most a constant number of times.

10. What Is DFS in a Graph?

Depth-First Search (DFS) explores as far as possible along one branch before backtracking. It can be implemented recursively or with an explicit stack.

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) {
    return;
  }

  visited.add(node);

  console.log(node);

  for (const neighbor of graph[node]) {
    dfs(graph, neighbor, visited);
  }
}

11. What Is the Difference Between BFS and DFS?

12. Why Do BFS and DFS Need a Visited Set?

Graphs can contain cycles. Without tracking visited vertices, a traversal could repeatedly follow the same edges and never terminate.

A → B
↑   ↓
└── C

A → B → C → A → B → C ...

Visited set prevents repeated processing.

13. How Do You Find Connected Components?

In an undirected graph, a connected component is a group of vertices where each vertex can reach every other vertex in that group. DFS or BFS can discover one component at a time.

function countComponents(graph) {
  const visited = new Set();
  let count = 0;

  for (const node of Object.keys(graph)) {
    if (visited.has(node)) {
      continue;
    }

    count++;

    const stack = [node];
    visited.add(node);

    while (stack.length > 0) {
      const current = stack.pop();

      for (const neighbor of graph[current]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          stack.push(neighbor);
        }
      }
    }
  }

  return count;
}

14. How Do You Detect a Cycle in an Undirected Graph?

During DFS, an already visited neighbor does not necessarily indicate a cycle because the neighbor may simply be the parent from which the current vertex was reached. Therefore, the parent must be tracked.

function hasCycleUndirected(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) {
          return true;
        }
      } else if (neighbor !== parent) {
        return true;
      }
    }

    return false;
  }

  for (const node of Object.keys(graph)) {
    if (
      !visited.has(node) &&
      dfs(node, null)
    ) {
      return true;
    }
  }

  return false;
}

15. How Do You Detect a Cycle in a Directed Graph?

A common DFS approach uses three states:

• Unvisited: the vertex has not been explored.
• Visiting: the vertex is currently in the DFS recursion path.
• Visited: exploration of the vertex is complete.

Finding an edge to a vertex currently marked as visiting indicates a directed cycle.

function hasCycleDirected(graph) {
  const state = {};

  function dfs(node) {
    state[node] = 1;

    for (const neighbor of graph[node]) {
      if (state[neighbor] === 1) {
        return true;
      }

      if (
        state[neighbor] !== 2 &&
        dfs(neighbor)
      ) {
        return true;
      }
    }

    state[node] = 2;
    return false;
  }

  for (const node of Object.keys(graph)) {
    if (
      state[node] === undefined &&
      dfs(node)
    ) {
      return true;
    }
  }

  return false;
}

16. What Is Topological Sorting?

Topological sorting produces an ordering of vertices in a directed acyclic graph such that for every directed edge u → v, u appears before v.

Learn HTML → Learn JavaScript → Learn React

Valid order:

HTML → JavaScript → React

Topological sorting is commonly used for prerequisites, build dependencies, course scheduling, and task ordering.

17. How Do You Perform Topological Sorting Using Kahn's Algorithm?

Kahn's algorithm uses indegree. Vertices with indegree zero are placed into a queue. Removing such a vertex decreases the indegree of its outgoing neighbors.

function topologicalSort(graph) {
  const indegree = {};

  for (const node of Object.keys(graph)) {
    indegree[node] = 0;
  }

  for (const node of Object.keys(graph)) {
    for (const neighbor of graph[node]) {
      indegree[neighbor]++;
    }
  }

  const queue = [];

  for (const node of Object.keys(indegree)) {
    if (indegree[node] === 0) {
      queue.push(node);
    }
  }

  const result = [];
  let front = 0;

  while (front < queue.length) {
    const node = queue[front++];

    result.push(node);

    for (const neighbor of graph[node]) {
      indegree[neighbor]--;

      if (indegree[neighbor] === 0) {
        queue.push(neighbor);
      }
    }
  }

  return result.length === Object.keys(graph).length
    ? result
    : null;
}

If fewer than V vertices are processed, the directed graph contains a cycle and a complete topological ordering does not exist.

18. What Is a Shortest Path in a Graph?

A shortest path is a path between vertices with the minimum total cost according to the problem's definition of distance.

The appropriate algorithm depends on the graph:

• Unweighted graph → BFS.
• Weighted graph with non-negative edges → Dijkstra's algorithm.
• Weighted graph that may contain negative edges → Bellman-Ford.
• All-pairs shortest paths → Floyd-Warshall can be used for appropriate graph sizes.

19. Why Does BFS Find Shortest Paths in an Unweighted Graph?

BFS explores vertices in increasing order of their number of edges from the source. Therefore, when a vertex is first reached, the path used to reach it contains the minimum possible number of edges.

Distance 0:
A

Distance 1:
B C

Distance 2:
D E F

Distance 3:
G

20. What Is Dijkstra's Algorithm?

Dijkstra's algorithm finds shortest paths from a source vertex to other vertices in a graph whose edge weights are non-negative.

It repeatedly selects the currently known closest unprocessed vertex and relaxes its outgoing edges.

Start A

A --4--> B
A --2--> C
C --1--> B

Initial:
dist(A) = 0
dist(B) = ∞
dist(C) = ∞

After A:
dist(B) = 4
dist(C) = 2

After C:
dist(B) = 3

21. Why Does Dijkstra Not Work with Negative Edge Weights?

Dijkstra's greedy choice relies on the assumption that once the closest unprocessed vertex is selected, no later path can produce a cheaper route through a negative edge. Negative weights can invalidate that assumption.

Bellman-Ford is designed to handle graphs that may contain negative edge weights and can also detect reachable negative cycles.

22. What Is Edge Relaxation?

Relaxation checks whether reaching a vertex through another vertex produces a shorter known distance.

if (
  distance[u] + weight < distance[v]
) {
  distance[v] =
    distance[u] + weight;
}

Relaxation is a central operation in Dijkstra's algorithm and Bellman-Ford.

23. What Is a Minimum Spanning Tree?

A minimum spanning tree (MST) of a connected, weighted, undirected graph is a spanning tree whose total edge weight is minimum.

A spanning tree connects all vertices without cycles and contains exactly V - 1 edges.

24. What Is the Difference Between Kruskal's and Prim's Algorithms?

25. What Is Union-Find and Where Is It Used in Graph Problems?

Union-Find, also called Disjoint Set Union (DSU), maintains groups of connected elements. It supports two key operations: finding the representative of a set and merging two sets.

It is commonly used by Kruskal's algorithm and can also be used for detecting cycles in undirected graphs.

Initially:

{A} {B} {C} {D}

Union(A, B):

{A, B} {C} {D}

Union(B, C):

{A, B, C} {D}

26. How Do You Detect a Cycle Using Union-Find?

For an undirected graph, process edges one at a time. If both endpoints already belong to the same set, adding the edge would connect vertices that are already connected and therefore creates a cycle.

Edge A-B:
Different sets → union

Edge B-C:
Different sets → union

Edge A-C:
Same set → cycle

27. What Is a DAG?

A DAG is a Directed Acyclic Graph. It contains directed edges and does not contain a directed cycle.

A → B → D
↓   ↓
C → E

DAGs are useful for representing prerequisites, build dependencies, workflows, and other directed dependency relationships.

28. How Do You Determine Whether a Graph Is Bipartite?

A graph is bipartite if its vertices can be divided into two groups so that every edge connects vertices from different groups.

A common approach is to use BFS or DFS to assign alternating colors to adjacent vertices. If an edge connects two vertices with the same color, the graph is not bipartite.

Color 0:
A C

Color 1:
B D

Every edge:
Color 0 ↔ Color 1

29. What Is the Difference Between a Path, Walk, and Cycle?

• Walk: a sequence of vertices connected by edges; vertices or edges may be revisited.
• Path: commonly refers to a route without repeating vertices, depending on the convention used.
• Cycle: a closed route that starts and ends at the same vertex, with the precise definition depending on the graph model.

In an interview, use the terminology expected by the problem and clarify definitions if they affect the solution.

30. How Do You Find the Shortest Path in a Grid?

A grid can be modeled as a graph where each valid cell is a vertex and neighboring cells are connected by edges.

If every move has equal cost, BFS is commonly used to find the shortest path.

Grid:

S . .
# . .
. . T

S = Start
T = Target
# = Blocked

BFS explores cells by distance.

31. How Do You Count Islands in a Grid?

A grid of cells can be interpreted as a graph. Each land cell connects to neighboring land cells. DFS or BFS can mark one island at a time.

1 1 0 0
1 0 0 1
0 0 1 1

Each connected group of 1s
represents one island.

The general pattern is to find an unvisited land cell, start a traversal, mark all connected land cells, and increment the island count.

32. How Do You Clone a Graph?

Graph cloning requires creating a new node for every original node and preserving the original adjacency relationships.

A map from original nodes to cloned nodes is commonly used so that cycles and repeated references can be handled correctly.

Original:

A → B
↑   ↓
└── C

Clone:

A' → B'
↑    ↓
└── C'

33. How Do You Find Whether a Path Exists Between Two Vertices?

BFS or DFS can determine whether a target vertex is reachable from a starting vertex. The traversal stops when the target is found or when all reachable vertices have been processed.

function hasPath(graph, start, target) {
  const stack = [start];
  const visited = new Set([start]);

  while (stack.length > 0) {
    const node = stack.pop();

    if (node === target) {
      return true;
    }

    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        stack.push(neighbor);
      }
    }
  }

  return false;
}

34. How Do You Reconstruct the Actual Shortest Path?

Finding the shortest distance is not always enough. To reconstruct the actual route, store a parent or predecessor for each vertex when its shortest distance is established.

parent[B] = A
parent[C] = B
parent[D] = C

Target:
D

Walk backward:

D → C → B → A

Reverse:

A → B → C → D

35. What Is the Complexity of BFS and DFS?

With an adjacency-list representation, both BFS and DFS run in: O(V + E).

• V = number of vertices.
• E = number of edges.

The traversal visits each reachable vertex and examines its adjacency relationships.

36. What Is the Complexity of BFS or DFS with an Adjacency Matrix?

With an adjacency matrix, finding all neighbors of a vertex requires scanning its entire row. A full BFS or DFS therefore commonly takes O(V²).

37. What Is the Difference Between a Shortest Path and a Minimum Spanning Tree?

A shortest-path algorithm finds a minimum-cost route between specified vertices. An MST connects all vertices with minimum total edge weight without cycles.

38. What Are Strongly Connected Components?

In a directed graph, a strongly connected component (SCC) is a maximal group of vertices where every vertex is reachable from every other vertex in the group.

A → B
↑   ↓
└── C

A, B, and C form a strongly
connected component.

Kosaraju's and Tarjan's algorithms are common algorithms for finding strongly connected components.

39. What Is a Negative Cycle?

A negative cycle is a cycle whose total edge weight is negative. If such a cycle is reachable from the source in a shortest-path problem, repeatedly traversing it can reduce the path cost without bound.

Bellman-Ford can be used to detect reachable negative cycles.

40. What Are Common Graph Interview Patterns?

41. How Do You Choose the Right Graph Algorithm?

Start by identifying the graph properties and the exact output required.

1. Determine whether the graph is directed or undirected.
2. Determine whether edges are weighted.
3. Check whether negative weights are possible.
4. Decide whether you need reachability, shortest distance, ordering, or connectivity.
5. For unweighted shortest paths, consider BFS.
6. For non-negative weighted shortest paths, consider Dijkstra.
7. For dependency ordering, consider topological sorting.
8. For minimum-cost connectivity, consider an MST algorithm.
9. For repeated connectivity merging, consider Union-Find.

Common Graph Interview Mistakes

Forgetting Cycles

Unlike trees, graphs can contain cycles. Always consider how visited vertices will be tracked.

Using BFS for Weighted Shortest Paths

BFS guarantees shortest paths measured by number of edges in an unweighted graph. Arbitrary positive edge weights require a weighted shortest-path algorithm.

Using Dijkstra with Negative Edges

Dijkstra relies on non-negative edge weights. If negative edges are allowed, consider Bellman-Ford instead.

Confusing MST with Shortest Path

An MST minimizes the total weight of a tree connecting all vertices. It does not generally minimize the path between every pair of vertices.

Ignoring Disconnected Graphs

A single traversal from one starting vertex may not visit every vertex. If the graph may be disconnected, iterate over all vertices and start a new traversal when needed.

Choosing the Wrong Representation

Adjacency lists are usually space-efficient for sparse graphs, while adjacency matrices can be useful when constant-time edge lookup is important.

Graph Interview Complexity Cheat Sheet

Adjacency List Space     → O(V + E)
Adjacency Matrix Space   → O(V²)

BFS                      → O(V + E)
DFS                      → O(V + E)

BFS with Matrix          → O(V²)
DFS with Matrix          → O(V²)

Unweighted Shortest Path → BFS
Non-negative Weighted     → Dijkstra
Negative Edges            → Bellman-Ford

Topological Sort         → O(V + E)
Kruskal                   → O(E log E)
Prim                      → Depends on implementation

Union-Find                → Near O(1) amortized
MST                       → V - 1 edges in a connected graph

Key variables:
V = vertices
E = edges

Graph Interview Quick Revision

Graph
├── Vertices + Edges
│
├── Representation
│   ├── Adjacency List
│   └── Adjacency Matrix
│
├── Traversal
│   ├── BFS → Queue
│   └── DFS → Stack / Recursion
│
├── Connectivity
│   ├── Connected Components
│   ├── Union-Find
│   └── SCC
│
├── Cycles
│   ├── Undirected → Parent / Union-Find
│   └── Directed → DFS State / Topological Sort
│
├── Shortest Path
│   ├── Unweighted → BFS
│   ├── Non-negative → Dijkstra
│   └── Negative Edges → Bellman-Ford
│
├── Ordering
│   └── Topological Sort
│
└── Minimum Spanning Tree
    ├── Kruskal
    └── Prim

Key Takeaways

• Graphs model relationships between vertices using edges.
• Always identify whether a graph is directed, weighted, cyclic, or disconnected.
• Adjacency lists are commonly used for sparse graphs.
• BFS uses a queue and is useful for shortest paths in unweighted graphs.
• DFS uses recursion or a stack and is useful for connectivity and cycle-related problems.
• Topological sorting is used for dependency ordering in DAGs.
• Dijkstra's algorithm requires non-negative edge weights.
• Bellman-Ford can handle negative edge weights and detect reachable negative cycles.
• Kruskal and Prim are common minimum spanning tree algorithms.
• Union-Find is useful for connectivity and undirected graph problems.
• Grid problems can often be transformed into graph traversal problems.
• For graph interviews, recognizing the problem pattern is often the first major step toward the solution.