Course contentsShow
← Computer Science
Lesson 705 of 2,87217. Graph Traversal AlgorithmsFree lesson

BFS with State Space Representation

BFS on implicit graphs: modeling states as nodes, generating neighbors dynamically, puzzle-solving applications.

BFS with State Space Representation

What You'll Learn

You'll learn how to apply BFS to implicit graphs where nodes represent states and edges represent state transitions, enabling you to solve puzzles and search problems without pre-building the entire graph.

The Core Idea

So far, you've used BFS on explicit graphs—graphs with pre-defined vertices and edges stored in memory. But many problems don't give you a graph upfront. Instead, they give you:

  • A starting state (initial configuration)
  • Rules for moving between states (allowed transitions)
  • A goal state (solution you're looking for)

With state space representation, each unique configuration becomes a node, and valid moves between configurations become edges. You generate these nodes and edges on-the-fly during BFS traversal.

Analogy: Think of a sliding tile puzzle. You don't store every possible board position beforehand—that would be millions of states! Instead, you start with the scrambled board, generate neighboring boards by sliding tiles, and explore until you reach the solved state.

How It Works

  1. Model the problem: Define what a "state" is (e.g., board configuration, robot position)
  2. Start BFS from the initial state
  3. Generate neighbors dynamically: For each state you dequeue, compute all valid next states using problem rules
  4. Track visited states: Use a set or hash table to avoid revisiting the same configuration
  5. Stop when goal found: BFS guarantees the shortest path in these unweighted implicit graphs

Example Applications

  • 8-puzzle/15-puzzle: States are board configurations
  • Water jug problems: States are (jugA, jugB) fill levels
  • Maze solving: States are (row, column) positions
  • String transformations: States are intermediate strings

Key Takeaway: BFS with state space representation lets you explore problem spaces as implicit graphs by generating states and transitions on-demand, making it perfect for puzzle-solving and planning problems where building the full graph is impractical.