Skip to content

topologicalSortKahn ​

topologicalSortKahn(graph) retorna uma ordenação topológica de um grafo acíclico direcionado. Aceita uma lista de adjacência ou Graph<N, W> e retorna ausência quando um ciclo impede a ordenação completa.

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

O resultado contém cada vértice uma vez. Um resultado opcional vazio indica um ciclo direcionado.

Exemplo ​

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

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

Resultado de estudo ​

tyrus
interface TopologicalSortKahnInfo {
    order: usize[];
    processedVertexCount: usize;
    examinedEdgeCount: usize;
    cycleDetected: bool;
    initialIndegrees: usize[];
    indegreeDecrementCount: usize;
    maxQueueSize: usize;
}
tyrus
import { TopologicalSortInfo, TopologicalSortKahnInfo, topologicalSortKahnInfo } from "tyrus:algorithm";
const info: TopologicalSortKahnInfo = topologicalSortKahnInfo([[1, 2], [3], [3], []]);
print(info.order); // [0, 1, 2, 3]
print(info.processedVertexCount); // 4
print(info.examinedEdgeCount); // 4
print(info.cycleDetected); // false
print(info.initialIndegrees); // [0, 1, 1, 2]
print(info.indegreeDecrementCount); // 4
print(info.maxQueueSize); // 2