Frontend School
DashboardProblemsLearnPracticeMock InterviewReportsStatsBuy Credits
DashboardProblemsLearnPracticeMock Interview
DSA for Frontend Engineers
  1. 1.Introduction to DSA for Frontend Engineers
  2. 2.JavaScript Fundamentals for DSA
  3. 3.Arrays and Strings: Core Techniques
  4. 4.Objects and Hash Maps in JavaScript
  5. 5.Linked Lists: Building Blocks
  6. 6.Stacks and Queues: LIFO & FIFO
  7. 7.Recursion and Iteration: Problem Solving Paradigms
  8. 8.Introduction to Trees: Binary Trees & BSTs
  9. 9.Tree Traversal Algorithms (BFS & DFS)
  10. 10.Sorting Algorithms I: Basics
  11. 11.Sorting Algorithms II: Divide & Conquer
  12. 12.Searching Algorithms: Linear & Binary Search
  13. 13.Graphs: Representation & Traversals
  14. 14.Dynamic Programming I: Memoization
  15. 15.Heaps and Priority Queues
  16. 16.Tries (Prefix Trees) for Autocomplete & Search
  17. 17.Advanced Graph Algorithms: Shortest Paths & MST
  18. 18.Dynamic Programming II: Tabulation & Frontend Patterns
  19. 19.Frontend System Design with DSA Lens
  20. 20.Interview Strategies & Advanced Problem Solving
DSA for Frontend Engineers
13

DSA · Lesson 13 of 20 · 4 min

Graphs: Representation & Traversals

Graph questions test if you can model abstract problems, a skill you use daily for component trees, routing, or state machines.

After this, you will know which graph representation to use in an interview (it's almost always the same one) and how to choose between the two main traversal algorithms, BFS and DFS. This is a foundational topic that unlocks a whole class of problems.

Choose Adjacency List

There are two ways to represent a graph: an adjacency matrix and an adjacency list. You should default to an adjacency list.

An adjacency list uses a map or hash table where keys are nodes and values are arrays of their neighbors. It's the standard choice because most graphs you encounter are "sparse," meaning nodes are connected to only a few other nodes.

This graph becomes a simple map:

{
  'A': ['B', 'C'],
  'B': ['D'],
  'C': ['E'],
  'D': ['E'],
  'E': []
}

The space complexity is O(V + E) (vertices + edges), which is efficient.

An adjacency matrix is a V x V grid where matrix[i][j] is 1 if an edge exists. Its space complexity is O(V^2), which is wasteful for sparse graphs. Its only real advantage is O(1) lookup to check if an edge exists between two specific nodes, but iterating over a node's neighbors takes O(V). With an adjacency list, neighbor iteration is proportional to the number of actual neighbors, which is usually much better.

Your interviewer might ask, "When would a matrix be better?" The textbook answer is for "dense graphs," where the number of edges E approaches V^2. This is rare. Stick with the adjacency list unless you have a very specific reason not to.

Pick the right traversal: BFS or DFS

Once you have your graph, you'll need to traverse it. The two workhorses are Breadth-First Search (BFS) and Depth-First Search (DFS).

BFS explores layer by layer. It starts at a source, visits all its direct neighbors, then their neighbors, and so on. It uses a queue (First-In, First-Out).

DFS goes as deep as it can down one path before backtracking. It starts at a source, picks a path, follows it to the end, then backs up and tries another. It uses a stack (Last-In, First-Out), which is often the implicit call stack in a recursive function.

The trap: Forgetting to track visited nodes. This is the most common way to fail a graph problem. Without a visited set, your traversal will get stuck in an infinite loop if the graph has a cycle. Always initialize a Set to keep track of nodes you've already seen.

When to use BFS vs. DFS

This is the core decision you'll make. The problem statement usually contains a strong hint.

Use BFS when the problem involves finding the shortest path in an unweighted graph. This is its main purpose. If you see "shortest," "fewest," or "minimum number of steps," think BFS. For example, finding the fewest clicks to navigate from one page to another in a site's link graph.

Use DFS for everything else:

  • Finding if a path exists between two nodes (any path, not necessarily the shortest).
  • Detecting cycles in a graph. This is a very common problem, like finding circular dependencies in a build system.
  • "Topological sorting," which is ordering nodes with dependencies (e.g., a build process).

If the problem asks for the "shortest path," use BFS. For "is there a path?" or "detect a cycle," use DFS. It's that simple most of the time.

How to implement a traversal

You need to be able to code at least one traversal from scratch. BFS is a great one to master because its iterative nature is explicit and easy to follow on a whiteboard.

This function takes an adjacency list, a starting node, and finds the shortest path distance to all other nodes.

function bfs(graph, startNode) {
  const distances = {};
  for (const node in graph) {
    distances[node] = Infinity;
  }
  distances[startNode] = 0;

  const queue = [startNode];
  const visited = new Set([startNode]);

  while (queue.length > 0) {
    const currentNode = queue.shift();
    const neighbors = graph[currentNode] || [];

    for (const neighbor of neighbors) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        distances[neighbor] = distances[currentNode] + 1;
        queue.push(neighbor);
      }
    }
  }
  return distances;
}

// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D'],
  'C': ['A', 'E'],
  'D': ['B', 'E', 'F'],
  'E': ['C', 'D'],
  'F': ['D']
};

console.log(bfs(graph, 'A'));
// { A: 0, B: 1, C: 1, D: 2, E: 2, F: 3 }

The time complexity is O(V + E) because we visit each vertex and check each edge exactly once. The space complexity is O(V) for the queue and visited set in the worst-case scenario (a graph that is a single long line).

DFS is often written recursively, where the call stack acts as the stack. Be prepared to write it iteratively as well, as it protects against stack overflow on very deep graphs. The iterative logic is identical to BFS; you just replace the queue.shift() with stack.pop().

Try it

Write a function hasCycle(graph) that takes a directed graph (as an adjacency list) and returns true if it contains a cycle. This is a classic DFS problem. Model a module dependency graph: { 'A': ['B'], 'B': ['C'], 'C': ['A'] } is a cycle. You'll need to track three states for each node: unvisited, visiting, and visited.

For more practice, try Clone Graph or find the number of connected components.

Next: Dynamic Programming I: Memoization.

Lock it in — apply this lesson under interview conditions.

Try a free mock interviewPractice this pattern
Previous

Searching Algorithms: Linear & Binary Search

Next

Dynamic Programming I: Memoization