tarjanScc
tarjanScc(graph) divide um grafo direcionado em componentes fortemente conexos usando a travessia de baixo elo de Tarjan. Aceita uma lista de adjacência ou Graph<N, W>.
| Assinatura | Retorno | Complexidade |
|---|---|---|
tarjanScc(graph: usize[][]) | usize[][] | O(V + E) |
tarjanScc(graph: Graph<N, W>) | usize[][] | O(V + E) |
Cada array interno contém vértices que alcançam uns aos outros. A ordem depende da travessia.
Exemplo
tyrus
import { tarjanScc } from "tyrus:algorithm";
const components: usize[][] = tarjanScc([[1], [0]]);
print(components.length); // 1Resultado de estudo
tyrus
interface TarjanSccInfo {
components: usize[][];
componentCount: usize;
examinedEdgeCount: usize;
stackOperationCount: usize;
discoveryIndices: usize[];
lowLinks: usize[];
stackPushCount: usize;
stackPopCount: usize;
}tyrus
import { SccInfo, TarjanSccInfo, tarjanSccInfo } from "tyrus:algorithm";
const info: TarjanSccInfo = tarjanSccInfo([[1], [2], [0, 3], [4], [3]]);
print(info.components); // [[4, 3], [2, 1, 0]]
print(info.componentCount); // 2
print(info.examinedEdgeCount); // 6
print(info.stackOperationCount); // 10
print(info.discoveryIndices); // [0, 1, 2, 3, 4]
print(info.lowLinks); // [0, 1, 2, 3, 4]
print(info.stackPushCount); // 5
print(info.stackPopCount); // 5