wire / wire-format / bfs-dfs
BFS (Breadth-First Search) explores vertices level by level using a queue. Finds shortest path (in unweighted graphs). DFS (Depth-First Search) explores as deep as possible using a stack/recursion. Used for: connected components, topological sort, cycle detection, strongly connected components (Tarjan/Kosaraju).
aka: BFS and DFS (graph traversal)
spec: Graph traversal
BFS (Breadth-First Search) explores vertices level by level using a queue. Finds shortest path (in unweighted graphs). DFS (Depth-First Search) explores as deep as possible using a stack/recursion. Used for: connected components, topological sort, cycle detection, strongly connected components (Tarjan/Kosaraju).
| field | size | meaning |
|---|---|---|
| BFS | O(V+E) | Queue-based. Explores all neighbors of current vertex before moving to next level. Finds shortest path in unweighted graphs. |
| DFS (recursive) | O(V+E) | Recursively visit unvisited neighbors. Uses call stack (O(V) space in worst case). |
| DFS (iterative) | O(V+E) | Explicit stack. Avoids recursion depth limits. |
| Topological sort | O(V+E) | DFS-based: push vertex to stack after all descendants visited. Or BFS (Kahn's algorithm): repeatedly remove vertices with in-degree 0. |
| SCC (Tarjan) | O(V+E) | Single DFS pass with low-link values. Finds strongly connected components in directed graphs. |
| Cycle detection | O(V+E) | DFS: if you reach a vertex that's in the current path (back edge), there's a cycle. |
example:
00 00
BFS/DFS (placeholder)
agent: curl -H 'accept: application/json' wire.phall.io/wire-format/bfs-dfs
or /wire-format/bfs-dfs.json