Skip to content

topologicalSortDfs ​

topologicalSortDfs(graph) calcula uma ordenação topológica com busca em profundidade. Aceita uma lista de adjacência ou Graph<N, W> e retorna ausência quando uma aresta de retorno revela um ciclo.

AssinaturaRetornoComplexidade
topologicalSortDfs(graph: usize[][])usize[]?O(V + E)
topologicalSortDfs(graph: Graph<N, W>)usize[]?O(V + E)

Cada vértice aparece uma vez. Um grafo com ciclo direcionado não possui ordenação topológica.

Exemplo ​

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

const order: usize[]? = topologicalSortDfs([[1], []]);
if (order) {
    print(order[1]);  // 1
}

Resultado de estudo ​

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]