Section 5.1Source:
server/src/analytics/traversal/GraphTraversal.tsIterative Breadth-First Search
Optimized BFS algorithm powering CodeGraph's multi-hop reachability analysis with O(1) queue indexing and shortest-path guarantees.
Source:
server/src/analytics/traversal/GraphTraversal.tsAlgorithmic Formulation
Breadth-First Search (BFS) explores vertices layer by layer. For code graph analysis, BFS is chosen over DFS for impact and dependency analysis because:
- Shortest-Distance Guarantee: The first time a node is reached during BFS, it is guaranteed to be via the minimum number of hops from the source.
- Accurate Depth Tracking: The hop depth
current.depth + 1accurately reflects architectural distance.
Complexity Analysis
Time Complexity: O(V + E) in the traversed subgraph, where $V$ is the number of visited nodes and $E$ is the number of incident edges.
Space Complexity: O(V) to maintain the visited set, queue array, and depthByNode map.