Skip to content

bfs ​

bfs(graph, start) visita los vértices alcanzables desde start en orden de anchura. La entrada puede ser una lista de adyacencia o un Graph<N, i32>; el resultado contiene los índices de los vértices en orden de visita.

Función ​

FirmaDevuelveDescripción
bfs(adj: usize[][], start: usize)usize[]Visita un grafo de lista de adyacencia en orden de anchura
bfs(graph: Graph<N, i32>, start: usize)usize[]Visita un Graph en orden de anchura

El vértice inicial debe estar dentro del grafo de entrada. El recorrido ignora los vértices que no son alcanzables desde start y marca cada vértice alcanzable como máximo una vez.

Complejidad ​

OperaciónComplejidad temporal
recorridoO(V + E)
memoriaO(V)

Ejemplos ​

lista de adyacencia ​

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]

Resultado de estudio ​

bfsInfo devuelve TraversalInfo con el orden de visita y métricas deterministas de frontera, profundidad y aristas.

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); // 2

entrada Graph ​

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]