Skip to content
Algorithm Atlas
Back to Benchmarks

Benchmark Family

Graph Traversal

Adjacency-list graph benchmarks for traversal, components, topological ordering, and cycle detection.

Generated

Apr 28, 2026, 12:07 PM

Measured

380

Skipped

1,300

Failures

0

Algorithms

8

Graph profiles

10

How to Read These Results

Benchmarks measure specific local JavaScript implementations on deterministic inputs. Results depend on runtime, hardware, implementation details, and input shape. They are not universal algorithm rankings.

BFS, DFS, components, topological sort, and cycle detection answer different graph questions, so summaries stay task-specific.

Contextual results

Algorithms Tested

Readable implementations included in this run

Breadth-First Search

Traversal From Start / Traversal Order

Queue-based breadth-first traversal from a start node.

DFS Iterative

Traversal From Start / Traversal Order

Stack-based depth-first traversal from a start node.

DFS Recursive

Traversal From Start / Traversal Order

Recursive depth-first traversal from a start node; skipped when recursion depth risk is high.

Connected Components

Connected Components / Component Labels

Iterative full-graph component labeling for undirected graphs.

Topological Sort (Kahn)

Topological Sort / Topological Order

Kahn's indegree-queue topological ordering for DAGs.

Topological Sort (DFS)

Topological Sort / Topological Order

Iterative DFS finishing-order topological ordering for DAGs.

Cycle Detection (Directed)

Cycle Detection / Cycle Boolean

Iterative color-state DFS cycle detection for directed graphs.

Cycle Detection (Undirected)

Cycle Detection / Cycle Boolean

Iterative parent-tracking DFS cycle detection for undirected graphs.

Graph profiles

Fixture coverage in this family

Path GraphStar GraphGrid GraphRandom Sparse UndirectedRandom Dense UndirectedRandom Sparse DirectedDag LayeredDag ChainDirected CycleDisconnected Components

Task types

Fixture coverage in this family

Traversal From StartConnected ComponentsTopological SortCycle Detection

Summary Findings

Careful takeaways from the generated benchmark data

  • Comparable groups are task-specific: traversal, components, topological sort, and cycle detection are not ranked together.
  • Recursive DFS is skipped on larger/deeper fixtures to avoid JavaScript call-stack risk.
  • Chart-ready data exists for future visualization work, but this page stays table-based.

Chart Previews

Static previews from the existing chart-ready benchmark exports. These charts are read-only summaries, not live benchmark execution or universal rankings.

Traversal Runtime on Grid Graphs

Median runtime by graph size for compatible traversal implementations on deterministic grid graphs.

median ms
0 ms0.54 ms1.08 ms10096110kBFS: 0.001 ms at 100BFS: 0.012 ms at 961BFS: 0.13 ms at 10000Iterative DFS: 0.001 ms at 100Iterative DFS: 0.01 ms at 961Iterative DFS: 0.096 ms at 10000Recursive DFS: 0.002 ms at 100Recursive DFS: 0.019 ms at 961nodesmedian ms
BFS
Iterative DFS
Recursive DFS

3 series, 8 plotted points. Unit: median ms.

Only traversal-from-start cases with start-0 are compared.

Traversal Work on Grid Graphs

Edges scanned by graph size. Work counters help explain behavior beyond timing noise.

edges scanned
021,38442,76810096110kBFS: 360 at 100BFS: 3,720 at 961BFS: 39,600 at 10000Iterative DFS: 360 at 100Iterative DFS: 3,720 at 961Iterative DFS: 39,600 at 10000Recursive DFS: 360 at 100Recursive DFS: 3,720 at 961nodesedges scanned
BFS
Iterative DFS
Recursive DFS

3 series, 8 plotted points. Unit: edges scanned.

Edges scanned are local instrumentation from these implementations.

Topological Sort Runtime

Median runtime for Kahn and DFS topological sort on the layered DAG fixture.

median ms
0 ms0.54 ms1.08 ms1001k10kKahn: 0.022 ms at 100Kahn: 0.093 ms at 1000Kahn: 0.149 ms at 10000Topo DFS: 0.023 ms at 100Topo DFS: 0.157 ms at 1000Topo DFS: 0.218 ms at 10000nodesmedian ms
Kahn
Topo DFS

2 series, 6 plotted points. Unit: median ms.

Topological sort previews include DAG fixtures only.

Compatibility Skips

Grouped skip reasons from the graph traversal benchmark summary.

skipped cases

4 bars. Unit: skipped cases.

Many skips are expected because graph algorithms answer different task-specific questions.

Task-Specific Summaries

Each task is summarized separately because the algorithms answer different graph questions.

TaskAlgorithmsProfilesMeasuredSkippedFailures
Traversal From StartBfs, Dfs Iterative +1Dag Chain, Dag Layered +8320400
Connected ComponentsConnected ComponentsDisconnected Components, Grid Graph +418120
Topological SortTopological Sort Kahn, Topological Sort DfsDag Chain, Dag Layered12480
Directed Cycle DetectionCycle Detection DirectedDag Chain, Dag Layered +21200
Undirected Cycle DetectionCycle Detection UndirectedDisconnected Components, Grid Graph +41800

Skip Reason Summary

Grouped skip reasons keep unsupported task/profile combinations explicit.

CategoryCountExample reason
Unsupported task1,170BFS is only run for traversal-from-start tasks
Requires directed graph78connected components benchmark skips directed graphs
Recursion depth risk40recursive DFS skipped for graphs above 1,000 nodes to avoid call-stack risk
Requires DAG12topological sort skips non-DAG profiles

Operation Metric Preview

Local normalized metrics can help explain behavior beyond raw timing.

AlgorithmTaskMedian nodesMedian edgesus/edge
BfsTraversal From Start7841,5520.005
Connected ComponentsConnected Components1,0003,8600.004
Cycle Detection DirectedCycle Detection5506250.013
Cycle Detection UndirectedCycle Detection1021980.022
Dfs IterativeTraversal From Start7841,5520.005
Dfs RecursiveTraversal From Start1003980.006

Graph-shape notes

Context for interpreting this family

  • path-graph stresses traversal depth and recursive DFS stack risk.
  • star-graph stresses high-degree hub adjacency scanning.
  • grid-graph provides spatially regular sparse connectivity.
  • random-dense-undirected increases edge scanning cost and is edge-capped.
  • DAG fixtures are the only valid topological-sort inputs.

Outputs

Generated benchmark artifacts used by this public page

graph-traversal-baseline.jsongraph-traversal-baseline-summary.jsongraph-traversal-baseline.mdgraph-traversal-baseline.csvgraph-traversal-chart-data.json

Limitations

Scope boundaries for this benchmark family

  • Synthetic adjacency-list graph fixtures only.
  • Dense graph edge counts are capped.
  • Recursive DFS is skipped above 1,000 nodes to avoid JavaScript call-stack risk.
  • Normalized per-node and per-edge metrics are derived local implementation measurements.
  • Memory usage and browser-runtime behavior are not measured.