PLAN-101 Career OS
Intermediate 45 Minutes

Graph Traversal: BFS, DFS and Visited Sets

Turn a graph into an adjacency list, reason about traversal order and avoid infinite cycles using visited nodes.

Key Learning Objectives

  • Represent a graph using neighbors for each vertex.
  • Implement breadth-first traversal.
  • Distinguish shortest unweighted distance from DFS reachability.
  • Handle cycles and disconnected components.

Draw vertices and edges before coding

A graph models relationships. An adjacency list stores neighbors for each vertex, usually using O(V+E) memory for V vertices and E edges. It suits sparse graphs because it does not allocate a dense V-by-V table. Decide whether edges are directed and whether a node can have a self-loop or repeated edge. Those details change expected traversal behavior.

BFS explores by layers

Breadth-first search uses a queue. Mark a node visited when you enqueue it, not when you remove it, so the same node is not placed in the queue repeatedly. In an unweighted graph, the first time you discover a node gives a shortest edge-count distance from the source. Every vertex and edge is processed at most a constant number of times, so traversal takes O(V+E) time.

function bfs(graph: Record<string, string[]>, start: string): string[] {
  const seen = new Set([start]);
  const queue = [start]; const order: string[] = [];
  for (let head = 0; head < queue.length; head++) {
    const node = queue[head]; order.push(node);
    for (const next of graph[node] || []) {
      if (!seen.has(next)) { seen.add(next); queue.push(next); }
    }
  }
  return order;
}

A head index avoids costly Array.shift calls; the visited set prevents repeated exploration.

DFS answers different questions

Depth-first search explores one branch before backtracking, often using recursion or an explicit stack. It is useful for connectivity, component counting and cycle-related algorithms; it does not generally find a shortest unweighted path without extra work. For a disconnected graph, a traversal from one source covers only its reachable component—loop over all vertices if your goal is to visit every component.

Build It: Campus connection explorer

Given a small graph of clubs and members, report reachability and minimum number of connections.

Project Deliverables

  • Adjacency-list representation.
  • BFS with distances.
  • DFS with component count.

Acceptance Criteria

  • Cycles do not loop forever.
  • Disconnected nodes remain unreachable.
  • Distance from a node to itself is zero.

Next Steps & Related Learning

This interactive lesson is part of the Data Structures & Algorithms curriculum. Continue exploring or try another interactive lesson:

View Full Data Structures & Algorithms → Arrays, Contiguous Memory & Hash Tables → JavaScript Asynchronous Execution & V8 Event Loop → Relational Database Architecture, B-Trees & Query Optimization → Semantic HTML, Accessible Forms & Document Structure → Python Functions, Dictionaries and Reliable Data Processing → SQL Joins, Missing Rows and Query Correctness → React State, Events and Derived UI → Designing a Task API: HTTP Methods, Errors and Validation → Sliding Window: From Quadratic Loops to a Linear Scan → Responsive CSS Layout: Flexbox, Grid and Fluid Constraints → TypeScript Union Types and Runtime Narrowing → Docker Images, Containers and Reproducible Builds → Git Branches, Pull Requests and Conflict Resolution → AWS IAM: Least Privilege and Secure Cloud Access → API Pagination, Error Contracts and Safe Retries →