Visualize & Master
Algorithms & Data Structures
Explore classic & modern sorting algorithms, efficient searching techniques, and interactive data structure visualizations — all with real-time step-by-step animation, comparisons, swaps, and Big-O metrics.
About Graph traversal algorithms systematically visit every reachable vertex
Graph traversal algorithms systematically visit every reachable vertex.
BFS (Breadth-First Search) explores level by level using a queue; DFS (Depth-First Search) explores as deep as possible along each branch using a stack (or recursion).
Both are foundational building blocks for dozens of higher-level algorithms.
How It Works
**BFS** enqueues the start node, then repeatedly dequeues a node and enqueues its unvisited neighbors.
This guarantees shortest-path distances on unweighted graphs.
**DFS** pushes the start node, pops it, marks it visited, then pushes all its neighbors.
DFS naturally reveals back edges (cycles), cross edges, and tree structure — used for topological sort, SCCs, and flood-fill.
Time & Space Complexities
| Operation | Time | Space |
|---|---|---|
| BFS Time | O(V + E) | O(V) |
| DFS Time | O(V + E) | O(V) |
| Shortest Path (unweighted) | O(V + E) via BFS | O(V) |
| Cycle Detection | O(V + E) via DFS | O(V) |
| Connected Components | O(V + E) | O(V) |
| Topological Sort (DFS) | O(V + E) | O(V) |
Best Use Cases
- BFS: shortest path in unweighted graphs (maze solving, social network distance)
- DFS: topological ordering, cycle detection, finding SCCs
- Web crawlers traversing hyperlinks
- Garbage collectors tracing reachable heap objects
- Puzzle solving (flood-fill, game state exploration)
Worked Example
BFS and DFS from A on a 6-node undirected graph
Input: A–B, A–C, B–D, B–E, C–E, C–F, E–D, E–F- 1 BFS: enqueue A, then its neighbors B and C, then the next layer D, E, F.
- 2 BFS visit order: A, B, C, D, E, F — nodes grouped strictly by distance from A.
- 3 BFS on this unweighted graph gives shortest-hop distances: B and C at distance 1, the rest at distance 2.
- 4 DFS: from A, go deep along B → D → E → C → F before backtracking.
- 5 DFS visit order: A, B, D, E, C, F — depth-first, so it can be used for cycle detection and topological ordering.
- 6 Both touch every vertex and edge exactly once, O(V + E).
Pseudocode
function BFS(graph, start):
visited = {start}
queue = [start]
while queue not empty:
u = dequeue(queue)
for each neighbor v of u:
if v not in visited:
visited.add(v)
enqueue(queue, v)
return visited function DFS(graph, start):
visited = {}
stack = [start]
while stack not empty:
u = pop(stack)
if u not in visited:
visited.add(u)
for each neighbor v of u:
push(stack, v)
return visited BFS — Breadth-First Search
Queue
Distances
| Node | Dist | Parent |
|---|
Result Order
SCC Groups
Distance Matrix
Select an algorithm and press Play to begin.