Web Simulation 

 

 

 

 

Graph Traversal & Search Algorithms Tutorial 

This interactive simulation visualizes the fundamental Graph Search and Traversal Algorithms. Understanding how to systematically explore graphs is essential for solving problems in pathfinding, network analysis, puzzle solving, and artificial intelligence.

What is Graph Traversal?

Graph traversal (or graph search) is the process of visiting all vertices in a graph in a systematic way. The two fundamental approaches are:

Algorithm Strategy Data Structure Properties
BFS
(Breadth-First Search)		 Explore all neighbors at the current depth before moving to the next level. Like ripples spreading from a stone dropped in water. Queue (FIFO)
First In, First Out		 Finds shortest path (unweighted), Level-order traversal
DFS
(Depth-First Search)		 Go as deep as possible along each branch before backtracking. Like exploring a maze by following one path to its end. Stack (LIFO)
Last In, First Out		 Memory efficient, Backtracking, Topological sort

Breadth-First Search (BFS)

BFS explores the graph in "layers" or "levels." Starting from a source node, it visits all nodes at distance 1, then all nodes at distance 2, and so on.

BFS Algorithm:
  1. Create a queue and enqueue the starting vertex
  2. Mark starting vertex as visited
  3. While queue is not empty:
    • Dequeue a vertex v
    • For each unvisited neighbor u of v:
      • Mark u as visited
      • Set distance[u] = distance[v] + 1
      • Enqueue u

Time Complexity: O(V + E) where V = vertices, E = edges

Space Complexity: O(V) for the queue

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses a stack (either explicit or via recursion) to keep track of the path.

DFS Algorithm:
  1. Create a stack and push the starting vertex
  2. While stack is not empty:
    • Peek at top vertex v
    • If v has an unvisited neighbor u:
      • Mark u as visited
      • Push u onto stack
    • Else: Pop v from stack (backtrack)

Discovery/Finish Times: DFS assigns timestamps to each vertex:

  • Discovery time: When the vertex is first visited
  • Finish time: When all descendants have been explored

Connected Components

A connected component is a maximal subgraph where every vertex is reachable from every other vertex within that subgraph.

Finding Connected Components:
  1. Initialize component counter = 0
  2. For each unvisited vertex v:
    • Run BFS/DFS from v
    • Mark all reachable vertices with current component ID
    • Increment component counter

Bipartite Graphs (2-Coloring)

A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set. Equivalently, the graph can be 2-colored with no adjacent vertices sharing the same color.

Bipartite Check Algorithm:
  1. Start BFS/DFS from any vertex, color it RED
  2. For each neighbor: assign opposite color (BLUE)
  3. If a neighbor already has the same color: NOT bipartite (odd cycle exists)
  4. If all vertices successfully colored: IS bipartite

Key Theorem: A graph is bipartite if and only if it contains no odd-length cycles.

Cycle Detection

Detecting cycles is crucial for many applications: dependency resolution, deadlock detection, and validating DAGs (Directed Acyclic Graphs). This simulation finds ALL cycles in the graph, not just the first one encountered.

Graph Type Cycle Detection Method
Undirected Graph During DFS, if we encounter an already-visited vertex (that isn't the parent), a cycle exists.
Directed Graph Maintain a recursion stack during DFS. If we find an edge to a vertex currently in the recursion stack, we've found a back edge, indicating a cycle.
Back Edge: In directed graphs, a back edge is an edge from a vertex to one of its ancestors in the DFS tree. Back edges are the definitive indicator of cycles in directed graphs.

Edge Classification (DFS)

DFS classifies edges into four types based on discovery/finish times:

Edge Type Description Condition
Tree Edge Edge to an unvisited vertex (part of DFS tree) Target is unvisited
Back Edge Edge to an ancestor (indicates cycle!) Target is in recursion stack
Forward Edge Edge to a descendant (non-tree) Target visited, discovery[u] < discovery[v]
Cross Edge Edge between unrelated vertices Target finished before u discovered

Applications

Algorithm Real-World Applications
BFS • GPS Navigation (shortest path in unweighted graphs)
• Social network "degrees of separation"
• Web crawlers (level-by-level exploration)
• Finding nearest neighbors
• Broadcasting in networks
DFS • Maze solving / Puzzle games
• Topological sorting (build systems, course prerequisites)
• Strongly connected components
• Detecting cycles in dependencies
• Path finding with constraints
Connected Components • Network reliability analysis
• Image segmentation
• Social network clustering
• Circuit analysis
Bipartite Check • Job assignment (workers ↔ tasks)
• Graph coloring / Scheduling
• Matching problems
• Conflict detection
Cycle Detection • Deadlock detection in OS
• Circular dependency in build systems
• Validating DAGs (Directed Acyclic Graphs)
• Detecting infinite loops

Breadth-First Search

Explores all neighbors at current depth before moving to next level. Uses a Queue (FIFO). Colors nodes by distance layers.

Queue

📝 Algorithm Log

Nodes: 0
Edges: 0
Default
Visiting
Visited
In Queue
In Stack
Back Edge / Conflict
Click: Add node | Drag: Move node | Shift+Drag: Create edge | Right-click: Delete node/edge

Usage Instructions

  1. Select Algorithm: Click the tabs at the top to choose which algorithm to visualize:
    • 🌊 BFS: Watch the "ripple" effect as nodes are explored layer by layer
    • 🐍 DFS: See the "snake-like" deep exploration with backtracking
    • 🎨 Components: Identify disconnected subgraphs (each gets a unique color)
    • 🔴🔵 Bipartite: Attempt to 2-color the graph
    • 🔄 Cycle: Detect cycles using back edge identification
  2. Build or Load Graphs:
    • Select a Preset from the dropdown for common graph structures
    • Click on empty canvas to add a node
    • Hold Shift and drag between nodes to create an edge
    • Right-click on a node or edge to delete it
    • Drag nodes to reposition them manually
    • Enable Auto-Layout to let nodes automatically spread apart using force-directed physics
  3. Control the Animation:
    • ▶ Run / ⏸ Pause: Toggle between running and paused (continues from current state)
    • ⏮ Step Bwd: Go back one step (undo)
    • ⏭ Step Fwd: Execute one step forward for detailed study
    • ↺ Reset: Clear algorithm state (keep graph)
    • Speed slider: Adjust animation speed
  4. Observe:
    • Queue/Stack: Watch the data structure fill and empty
    • Algorithm Log: Step-by-step explanation of what's happening
    • Node Colors: Visual state changes as algorithm progresses
    • DFS Times: Discovery/Finish times shown above nodes

Preset Graphs

Preset Description Best For
Simple Graph 5-node connected graph with moderate connectivity BFS/DFS basic demonstration
Binary Tree 7-node tree structure (depth 3) Comparing BFS (level-order) vs DFS (pre-order)
Graph with Cycle Pentagon with extra diagonal edge Cycle detection, bipartite failure (odd cycle)
Disconnected Two separate components (triangle + square) Connected components algorithm
Bipartite Graph Two groups with edges only between groups Successful 2-coloring demonstration
Non-Bipartite Simple triangle (odd cycle) Bipartite check failure case
Directed with Cycle 4 nodes in cycle + center node (directed) Directed cycle detection with back edge
DAG Directed Acyclic Graph (6 nodes, top-down flow) Showing no cycle exists

Algorithm Comparison

Aspect BFS DFS
Data Structure Queue (FIFO) Stack (LIFO) / Recursion
Exploration Pattern Level by level (breadth) Path by path (depth)
Shortest Path ✓ Yes (unweighted) ✗ No
Memory Usage O(V) - can be large O(h) - height of tree
Complete Search ✓ Always finds solution ✓ Always finds solution
Time Complexity O(V + E) O(V + E)

Key Observations to Make

Experiment What to Observe
BFS on Binary Tree Nodes visited level by level (root → children → grandchildren). Layer colors show distance from start.
DFS on Binary Tree Deep path exploration first. Watch the stack grow as we go deep, then shrink on backtrack. Note discovery/finish times.
Components on Disconnected Each component gets a unique color. Algorithm restarts from new unvisited node when one component is exhausted.
Bipartite on Triangle Fails! Three vertices in a cycle cannot be 2-colored. Conflict edge shown in red.
Bipartite on Bipartite Graph Succeeds! Left group gets RED, right group gets BLUE. No conflicts.
Cycle on Directed-Cycle The algorithm finds ALL cycles, not just the first one. Watch as multiple back edges are detected and highlighted in red!
Cycle on DAG No cycle found. All edges are tree edges or forward edges. Graph is valid for topological sorting.
Use Step Bwd Step backward through the algorithm to review previous states. Great for understanding how BFS queue or DFS stack evolves!

Understanding the Visualization

Node Colors:

  • Default - Not yet discovered
  • Visiting - Currently being processed
  • Visited - Completely explored
  • In Queue - Waiting in BFS queue
  • In Stack - Currently in DFS stack

BFS Layer Colors: In BFS, visited nodes are colored by their distance from the start node:

  • Layer 0 = Start node (distance 0)
  • Layer 1 = Distance 1
  • Layer 2 = Distance 2
  • Layer 3 = Distance 3
  • Layer 4 = Distance 4
  • Layer 5+ = Distance 5+

DFS Timestamps: Numbers shown above nodes in format discovery/finish:

  • Discovery time: When the node is first encountered
  • Finish time: When all descendants have been explored
  • A node is an ancestor of another if its discovery time is less and finish time is greater

Pseudocode Reference

BFS(G, start):
  queue ← [start]
  visited[start] ← true
  distance[start] ← 0
  while queue not empty:
    v ← dequeue(queue)
    for each neighbor u of v:
      if not visited[u]:
        visited[u] ← true
        distance[u] ← distance[v] + 1
        enqueue(queue, u)
DFS(G, v):
  visited[v] ← true
  discovery[v] ← time++
  for each neighbor u of v:
    if not visited[u]:
      DFS(G, u)
  finish[v] ← time++
HasCycle(G):
  visited ← ∅
  recStack ← ∅
  for each vertex v in G:
    if v not in visited:
      if CycleDFS(v): return true
  return false

CycleDFS(v):
  visited.add(v)
  recStack.add(v)
  for each neighbor u of v:
    if u in recStack: return true // Back edge!
    if u not in visited and CycleDFS(u): return true
  recStack.remove(v)
  return false

Complexity Analysis

Algorithm Time Space Notes
BFS O(V + E) O(V) Queue can hold up to V vertices
DFS (iterative) O(V + E) O(V) Stack depth bounded by V
DFS (recursive) O(V + E) O(V) Call stack depth bounded by V
Connected Components O(V + E) O(V) Single pass through all vertices
Bipartite Check O(V + E) O(V) Modified BFS/DFS with coloring
Cycle Detection O(V + E) O(V) DFS with recursion stack tracking

Simulation Features

Feature Description
▶ Run / ⏸ Pause Toggle Single button that starts, pauses, and resumes the algorithm. Continues from current state when resumed.
⏮ Step Bwd / ⏭ Step Fwd Navigate through algorithm execution one step at a time. Step backward restores previous state including node colors, log entries, and data structures.
Auto-Layout (Force-Directed) When enabled, nodes automatically spread apart using physics simulation. Uses repulsion forces between all nodes and spring attraction for connected nodes.
Find ALL Cycles Unlike typical implementations that stop at the first cycle, this simulation continues to find and highlight all back edges (cycles) in the graph.
History Tracking Each step saves the complete state (node properties, edge types, log content) allowing full rewind capability up to 100 steps.

Force-Directed Layout Physics

The Auto-Layout feature uses a force-directed graph drawing algorithm inspired by Fruchterman-Reingold:

Physics Model:

Repulsion (Coulomb's Law):
  Frepel = repulsion / distance²
  Applied between ALL pairs of nodes

Attraction (Hooke's Law - Springs):
  Fattract = springK × (distance - idealLength)
  Applied only to connected nodes (edges act as springs)

Center Gravity:
  Weak pull toward canvas center to keep graph visible

Damping:
  Velocity reduced each frame to reach equilibrium