Depth-first search
Algorithms AIMech:DepthFirstSearch DRAFT
Aliases: DFS, Depth first traversal
A graph or state-space traversal that follows a newly chosen successor down the current search branch and backtracks when that branch has no eligible unvisited successor or reaches a stopping boundary.
Identity Notes & Concept Scope
DFS denotes depth-first traversal, not depth-first iterative deepening or a shortest-path cost ordering. The visited-vertex graph traversal and a path-only tree search share the depth-first order but have different duplicate handling and memory requirements. No normalized identity match was found across the 442 AIO and 119 prior native records; ignored-inclusive text hits in the main checkout were dependency-package documentation and an unrelated package-metadata substring, not existing concept records.
Claims & Grounded Evidence
2 Claims
Mechanism
#search-procedure
A recursive call or explicit stack continues down a successor branch before resuming the remaining successors of its ancestors. In the cited graph traversal, discovered vertices are marked and skipped on later encounters; an outer traversal can restart at an undiscovered vertex after a reachable component is exhausted.
Limitation
#tree-search-limitations
The paper’s path-only depth-first search can revisit states along different paths, and an unbounded search without duplicate checks may fail to terminate. A chosen depth cutoff can miss a goal or permit a nonshortest first solution.
⚠️ Curated Limitations & Negative Results
- Depth-first order alone does not guarantee that the first goal has a shortest path.
- A tree expansion can follow an infinite branch or repeat states indefinitely unless appropriate limits or duplicate controls are applied.
- The graph implementation retains vertex marks; the linear-in-depth memory description of a path-only search is not a universal memory bound for all DFS implementations.
Artificial Intelligence Ontology (AIO) Grounding
Explicit AIO Snapshot Assessment: No Match
Rationale: No suitable AIO counterpart for this graph/state-space search procedure was identified in the inspected snapshot. Using graphs, evaluation functions or a search subroutine in an AI system does not equate the algorithm with a learned model, a learning task or a mathematical function.
Search Scope: All 442 pinned AIO labels and scoped synonyms and 119 preceding native identities were compared. Both updated checkouts were searched including hidden and ignored files. Exact CLASS nodes and edges for GraphLanguageModel, ReasoningLLM, NeuroSymbolicLLM, MachineLearningTask, MathematicalFunction and ReinforcementLearning were inspected, alongside semantic search for search, planning, heuristic, path, traversal, symbolic, reasoning and graph terminology.
| Examined AIO Candidate | Rejection Reason |
|---|---|
AIO:GraphLanguageModel
|
A language model operating on structured graph representations is not a graph traversal or shortest-path algorithm. |
AIO:ReasoningLLM
|
Language-task deductive inference does not denote general state-space search. |
AIO:NeuroSymbolicLLM
|
A language-model architecture combining neural and symbolic components is not the search procedure itself. |
AIO:MachineLearningTask
|
Building methods that learn from data is not the identity of an algorithm traversing a specified graph. |
AIO:MathematicalFunction
|
The search procedure is distinct from the mathematical functions it may evaluate. |
AIO:ReinforcementLearning
|
A learning task balancing exploration and exploitation is distinct from deterministic graph/state-space traversal. |
Evidence Sources & Primary Literature
2 Sources| Source ID | Publication / Document | Type / Access | Reference & Checksum |
|---|---|---|---|
method-source
|
Jeremy Siek
|
official documentation
documentation
|
sha256:68ba0b3d02ba…
|
search-paper
|
Richard E. Korf
|
primary paper
full_text
|
ID: doi:10.1016/0004-3702(85)90084-0
sha256:44fc92b6885a…
|
Curation Provenance
Curator: Codex
Method: ai_assisted
Model: GPT-6
Created: 2026-10-11T05:32:15Z
Updated: 2026-10-11T05:32:31Z
Source File:
data/curated/DepthFirstSearch.yaml