topologicalSortKahn
topologicalSortKahn(graph) devuelve un orden topológico de un grafo acíclico dirigido. Acepta una lista de adyacencia o Graph<N, W> y devuelve ausencia cuando un ciclo impide completar el orden.
| Firma | Retorno | Complejidad |
|---|---|---|
topologicalSortKahn(graph: usize[][]) | usize[]? | O(V + E) |
topologicalSortKahn(graph: Graph<N, W>) | usize[]? | O(V + E) |
El resultado contiene cada vértice una vez. Un resultado opcional vacío indica un ciclo dirigido.
Ejemplo
tyrus
import { topologicalSortKahn } from "tyrus:algorithm";
const order: usize[]? = topologicalSortKahn([[1], []]);
if (order) {
print(order[0]); // 0
}Resultado de estudio
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