Interview OS
Back to Algorithms & Data Structures

Library

Graph traversal (BFS/DFS)

Explore connectivity and shortest hops.

Graph

Overview

Graph traversal (BFS and DFS) systematically visits every reachable node without repeats. It underpins connectivity, component counting, cycle detection, and topological ordering.

How it works

Graph
StartFrontierVisitOutputSourceseenQueue/StackFIFO/LIFONeighborsadjReach/order
ClientAsyncServiceData

Step by step, with examples

  1. 1

    Source

    • Init the visited set.
  2. 2

    Queue/Stack

    • BFS explores by level; DFS by depth.
  3. 3

    Neighbors

    • Mark and expand each neighbor.
  4. 4

    Reach/order

    • Return reachability or an order.
    • Example: components

Overview

BFS finds shortest unweighted paths; DFS explores depth, powers topological sort and cycle detection.

When to use it

  • Shortest path (unweighted)
  • Connected components
  • Dependency ordering

Common pitfalls

  • No visited set -> infinite loops
  • Recursion depth on large graphs

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides