bfs
bfs(graph, start) visits the vertices reachable from start in breadth-first order. The input can be an adjacency list or a Graph<N, i32>; the result contains vertex indices in visitation order.
Function
| Signature | Returns | Description |
|---|---|---|
bfs(adj: usize[][], start: usize) | usize[] | Visits an adjacency-list graph in breadth-first order |
bfs(graph: Graph<N, i32>, start: usize) | usize[] | Visits a Graph in breadth-first order |
The starting vertex must be within the input graph. The traversal ignores vertices that are not reachable from start and marks each reachable vertex at most once.
Complexity
| Operation | Time Complexity |
|---|---|
| traversal | O(V + E) |
| memory | O(V) |
Examples
adjacency list
tyrus
import { bfs } from "tyrus:algorithm";
const graph: usize[][] = [[1, 2], [3], [3], []];
const order: usize[] = bfs(graph, 0);
print(order); // [0, 1, 2, 3]Study result
bfsInfo returns TraversalInfo with the visit order and deterministic frontier, depth, and edge metrics.
tyrus
interface TraversalInfo {
start: usize;
visitOrder: usize[];
visitedCount: usize;
examinedEdgeCount: usize;
maxFrontierSize: usize;
maxDepth: usize;
}tyrus
import { TraversalInfo, bfsInfo } from "tyrus:algorithm";
const info: TraversalInfo = bfsInfo([[1, 2], [3], [3], []], 0);
print(info.visitOrder); // [0, 1, 2, 3]
print(info.visitedCount); // 4
print(info.examinedEdgeCount); // 4
print(info.maxFrontierSize); // 2
print(info.maxDepth); // 2Graph input
tyrus
import { Graph, bfs } from "tyrus:algorithm";
const graph = Graph<i32, i32>();
graph.addEdge(0, 1, 1);
graph.addEdge(0, 2, 1);
graph.addEdge(1, 3, 1);
const order: usize[] = bfs(graph, 0);
print(order); // [0, 1, 2, 3]