Breadth-first search
Algorithms AIMech:BreadthFirstSearch DRAFT
Aliases: BFS, Breadth first traversal
A graph or state-space traversal that expands vertices in nondecreasing shortest-path distance from a start vertex, where distance counts edges.
Identity Notes & Concept Scope
BFS denotes breadth-first search in this record, not the abbreviation sometimes used for generic best-first search. FIFO layer traversal is distinct from a cost-priority queue for weighted paths and from depth-first traversal. 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 FIFO queue holds discovered vertices awaiting expansion. Remove its front vertex, inspect its outgoing edges, mark each previously undiscovered neighbor when it is enqueued, and continue until the queue is empty or a goal-search stopping condition is met.
Scope
#edge-count-scope
Unit-edge paths are within breadth-first search’s shortest-path scope; general nonnegative weighted paths require a cost-sensitive method such as Dijkstra’s algorithm.
⚠️ Curated Limitations & Negative Results
- Shortest distance means number of edges; arbitrary unequal edge costs are not minimized by FIFO traversal.
- The cited graph implementation tracks discovered vertices. Its visited-state storage and frontier memory must not be confused with a path-only tree-search implementation.
- Traversal from a single start reaches only its reachable component; the documentation describes separate visits for disconnected components.
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:2a265e09d076…
|
versioned-documentation-scope
|
Jeremy Siek
|
official documentation
documentation
|
sha256:3bcfc6120324…
|
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/BreadthFirstSearch.yaml