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.
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:
Create a queue and enqueue the starting vertex
Mark starting vertex as visited
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:
Create a stack and push the starting vertex
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:
Initialize component counter = 0
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:
Start BFS/DFS from any vertex, color it RED
For each neighbor: assign opposite color (BLUE)
If a neighbor already has the same color: NOT bipartite (odd cycle exists)
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
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
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
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
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