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
| Firma | Devuelve | Descripció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ón | Complejidad temporal |
|---|---|
| recorrido | O(V + E) |
| memoria | O(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); // 2entrada 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]