Skip to content
Deadline to Die

Module 2: Graph Traversal (The Web Crawler)

📚 Module 2: Graph Traversal

Course ID: DSA-304
Subject: The Web Crawler

How do you visit every node in a graph? Unlike a Tree, a Graph can have Cycles (loops). If you aren’t careful, you will walk in circles forever! We use two strategies: BFS and DFS.

🏗️ Step 1: Breadth-First Search (The “Ripple”)

BFS explores the graph in “Layers.”

🧩 The Analogy: The Pebble in the Pond

  • You drop a pebble in the water (The Start Node).
  • The ripple hits all the closest nodes first (Level 1).
  • Then it hits the next set of nodes (Level 2).
  • Rule: We use a Queue (Milestone 3) to keep track of who to visit next.

🏗️ Step 2: Depth-First Search (The “Labyrinth”)

DFS explores as far as possible along each branch before backtracking.

🧩 The Analogy: The Maze

  • You walk down a path until you hit a dead end.
  • You turn around (Backtrack) to the last intersection and try a different path.
  • Rule: We use a Stack (Milestone 3) to keep track of our path.

🏗️ Step 3: Preventing Infinite Loops (The “Breadcrumbs”)

Since graphs can have cycles, you MUST keep a list of Visited nodes.

  • When you arrive at a node, you ask: “Have I been here before?”
  • If Yes, stop and turn around.
  • If No, mark it as “Visited” and continue.

🥅 Module 2 Review

  1. BFS: Best for finding the Shortest Path on an unweighted graph.
  2. DFS: Best for finding if a path Exists at all.
  3. Visited Set: Mandatory for preventing infinite loops.

:::tip Senior Tip When you search for a route in Google Maps, it uses an optimized version of BFS called Dijkstra’s Algorithm. It picks the “shortest” edge instead of just any edge! ::: Riverside. Riverside.