topologicalSortDfs
topologicalSortDfs(graph) calcula un orden topológico mediante búsqueda en profundidad. Acepta una lista de adyacencia o Graph<N, W> y devuelve ausencia si una arista de retorno revela un ciclo.
| Firma | Retorno | Complejidad |
|---|---|---|
topologicalSortDfs(graph: usize[][]) | usize[]? | O(V + E) |
topologicalSortDfs(graph: Graph<N, W>) | usize[]? | O(V + E) |
Cada vértice aparece una vez. Un grafo con ciclo dirigido no tiene orden topológico.
Ejemplo
tyrus
import { topologicalSortDfs } from "tyrus:algorithm";
const order: usize[]? = topologicalSortDfs([[1], []]);
if (order) {
print(order[1]); // 1
}Resultado de estudio
tyrus
interface TopologicalSortDfsInfo {
order: usize[];
processedVertexCount: usize;
examinedEdgeCount: usize;
cycleDetected: bool;
finalStates: usize[];
maxDepth: usize;
backEdge: [usize, usize]?;
}tyrus
import { TopologicalSortDfsInfo, TopologicalSortInfo, topologicalSortDfsInfo } from "tyrus:algorithm";
const info: TopologicalSortDfsInfo = topologicalSortDfsInfo([[1, 2], [3], [3], []]);
print(info.order); // [0, 2, 1, 3]
print(info.processedVertexCount); // 4
print(info.examinedEdgeCount); // 4
print(info.cycleDetected); // false
print(info.finalStates); // [2, 2, 2, 2]
print(info.maxDepth); // 3
print(info.backEdge ?? [9usize, 9usize]); // [9, 9]