Skip to content

dfs ​

dfs(graph, start) visita los vértices alcanzables desde start en orden iterativo de profundidad. 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
dfs(adj: usize[][], start: usize)usize[]Visita un grafo de lista de adyacencia en orden iterativo de profundidad
dfs(graph: Graph<N, i32>, start: usize)usize[]Visita un Graph en orden iterativo de profundidad

El vértice inicial debe estar dentro del grafo de entrada. Los vecinos se procesan en orden inverso de inserción en la pila para que el resultado siga el mismo orden que un recorrido recursivo sobre la lista de adyacencia.

Complejidad ​

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

Ejemplos ​

lista de adyacencia ​

tyrus
import { dfs } from "tyrus:algorithm";

const graph: usize[][] = [[1, 2], [3], [3], []];
const order: usize[] = dfs(graph, 0);

print(order);  // [0, 1, 3, 2]

Resultado de estudio ​

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

tyrus
interface TraversalInfo {
    start: usize;
    visitOrder: usize[];
    visitedCount: usize;
    examinedEdgeCount: usize;
    maxFrontierSize: usize;
    maxDepth: usize;
}
tyrus
import { TraversalInfo, dfsInfo } from "tyrus:algorithm";

const info: TraversalInfo = dfsInfo([[1, 2], [3], [3], []], 0);
print(info.visitOrder); // [0, 1, 3, 2]
print(info.visitedCount); // 4
print(info.examinedEdgeCount); // 4
print(info.maxFrontierSize); // 2
print(info.maxDepth); // 2

entrada Graph ​

tyrus
import { Graph, dfs } 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[] = dfs(graph, 0);
print(order);  // [0, 1, 3, 2]