dfs
dfs(graph, start) visita os vértices alcançáveis a partir de start em ordem iterativa de profundidade. A entrada pode ser uma lista de adjacência ou um Graph<N, i32>; o resultado contém os índices dos vértices na ordem de visita.
Função
| Assinatura | Retorna | Descrição |
|---|---|---|
dfs(adj: usize[][], start: usize) | usize[] | Visita um grafo em lista de adjacência em ordem iterativa de profundidade |
dfs(graph: Graph<N, i32>, start: usize) | usize[] | Visita um Graph em ordem iterativa de profundidade |
O vértice inicial deve estar dentro do grafo de entrada. Os vizinhos são processados na ordem inversa de inserção na pilha, para que o resultado siga a mesma ordem de uma travessia recursiva sobre a lista de adjacência.
Complexidade
| Operação | Complexidade Temporal |
|---|---|
| travessia | O(V + E) |
| memória | O(V) |
Exemplos
lista de adjacência
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 estudo
dfsInfo retorna TraversalInfo com a ordem de visita e métricas determinísticas de pilha, profundidade e arestas.
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]