AlgorandSIMULATION v1.0
Sequential Engines(17)
Parallel Engines

Depth-First Search (DFS)

sequentialRAM

An algorithm for traversing or searching tree or graph data structures, exploring as deep as possible along each branch before backtracking.

SIMULATION STEP PROGRESSStep 1 / 1
SPEED (50%)
Code Workspace
1procedure DFS(G, start_node)
2 let S be a stack
3 label start_node as discovered
4 S.push(start_node)
5 while S is not empty do
6 v := S.pop()
7 for each neighbor w of v do
8 if w is not labeled as discovered then
9 label w as discovered
10 S.push(w)
11 end if
12 end for
13 end while
14end procedure
Currently highlights executing branch
RUNTIME COST METRICS
Comparisons0
Memory Writes0
Memory Reads0
Elements Swapped0
Computational Model:RAM (Single Core)
Theoretical Bound:O(V + E)
Space Complexity:O(V)
Communication Cost:0 (Shared Bus)
THEORETICAL ANALYSIS & RESEARCH

Conceptual Focus: An algorithm for traversing or searching tree or graph data structures, exploring as deep as possible along each branch before backtracking.

Real-world Industrial Applications:
  • Finding connected components and strongly connected components
  • Topological sorting of Directed Acyclic Graphs (DAGs)
  • Solving maze puzzles and game decision trees