wire / wire-format / bfs-dfs

BFS and DFS (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).

wire-format kind wire-format status standard verification verified tier B wire-format@1

aka: BFS and DFS (graph traversal)

wire format

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).

fieldsizemeaning
BFSO(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 sortO(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 detectionO(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)


provenance

agent: curl -H 'accept: application/json' wire.phall.io/wire-format/bfs-dfs or /wire-format/bfs-dfs.json