DSAMonth 1 · Week 4

Day 20: Basic Graph Traversals (Adjacency Matrix/List)

Represent graphs correctly and apply BFS/DFS to non-tree structures, handling the one thing trees never require: cycle-safe visited tracking.

Mark this day complete

Study

Concepts

Adjacency list vs adjacency matrix

Adjacency list: a Map/array where each node stores only its actual neighbors — O(V + E) space, and iterating a node's neighbors is O(degree). This is the default choice for sparse, real-world graphs (social networks, dependency graphs, road networks). Adjacency matrix: a V×V grid where `matrix[i][j] = 1` means an edge exists — O(V²) space, but O(1) edge-existence checks. Only worth it for dense graphs or when you need constant-time "are these two directly connected?" queries.

Graphs need explicit visited tracking — trees do not

Trees have no cycles by definition, so tree DFS/BFS never revisits a node. General graphs can have cycles (and multiple paths to the same node), so every graph traversal MUST maintain a `visited` Set and check/mark it before recursing/enqueueing — omitting this causes either infinite loops (on a cycle) or redundant work (revisiting the same node via a different path).

For directed graphs, DFS with a "currently in recursion stack" set (distinct from "ever visited") is the standard technique to detect cycles — a back-edge to a node still on the current path means a cycle; a back-edge to a node already fully processed and off the path does not.

See It

Visualizations

Visualization

A small directed graph and its adjacency list

A → B, A → C, B → D, C → D, D → A (cycle!).

Build It

Code Examples

Build an adjacency list, then run BFS and DFS

const edges = [['A', 'B'], ['A', 'C'], ['B', 'D'], ['C', 'D'], ['D', 'A']];

function buildAdjList(edges) {
  const graph = new Map();
  for (const [from, to] of edges) {
    if (!graph.has(from)) graph.set(from, []);
    if (!graph.has(to)) graph.set(to, []);
    graph.get(from).push(to); // directed: only from -> to
  }
  return graph;
}

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

  while (queue.length) {
    const node = queue.shift();
    order.push(node);
    for (const neighbor of graph.get(node) ?? []) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor); // mark visited at ENQUEUE time
        queue.push(neighbor);
      }
    }
  }
  return order;
}

const graph = buildAdjList(edges);
console.log(bfs(graph, 'A')); // ['A', 'B', 'C', 'D']

Detect a cycle in a directed graph — recursion-stack technique

function hasCycle(graph) {
  const visited = new Set();   // ever visited, across the whole graph
  const inStack = new Set();   // currently on THIS path (recursion stack)

  function dfs(node) {
    visited.add(node);
    inStack.add(node);

    for (const neighbor of graph.get(node) ?? []) {
      if (inStack.has(neighbor)) return true;       // back-edge -> cycle!
      if (!visited.has(neighbor) && dfs(neighbor)) return true;
    }

    inStack.delete(node); // done exploring this node's path — un-choose
    return false;
  }

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

Remember

Key Takeaways

Adjacency list (Map<node, neighbors[]>) is the default for sparse real-world graphs — O(V+E) space.
Adjacency matrix trades O(V²) space for O(1) edge-existence checks — only worth it for dense graphs.
Graphs need explicit visited tracking to avoid infinite loops on cycles — trees never need this.
Directed-cycle detection needs TWO sets: visited (ever seen) and inStack (on the current path) — a back-edge into inStack means a cycle.
BFS/DFS mechanics are identical to tree traversal — the only new rule is "check visited before you go".

Do It

Practice

1Build an undirected graph adjacency list and write a function counting the number of connected components.
2Solve "Course Schedule" (detect if a set of prerequisites has a valid order) using the directed-cycle-detection technique.
3Implement the same BFS using an adjacency matrix instead of a list, and compare code complexity for a graph with 6 nodes.