Skip to content

biconnectedComponents ​

biconnectedComponents(graph) decompõe um grafo não direcionado em componentes biconexos de arestas usando uma travessia de baixo elo. Aceita uma lista de adjacência ou Graph<N, W>.

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

Cada array interno contém as arestas de um componente como pares de vértices. Pontes formam componentes unitários.

Exemplo ​

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

const components: [usize, usize][][] = biconnectedComponents([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(components.length); // 2

Resultado para estudo ​

biconnectedComponentsInfo retorna BiconnectedComponentsInfo, com componentes copiados e métricas low-link compartilhadas.

tyrus
interface BiconnectedComponentsInfo {
    examinedEdgeCount: usize;
    discoveryIndices: usize[];
    lowLinks: usize[];
    resultCount: usize;
    components: [usize, usize][][];
}
tyrus
import { BiconnectedComponentsInfo, ConnectivityInfo, biconnectedComponentsInfo } from "tyrus:algorithm";
const info: BiconnectedComponentsInfo = biconnectedComponentsInfo([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(info.components); // [[ [1, 3] ], [ [2, 0], [1, 2], [0, 1] ]]
print(info.examinedEdgeCount); // 8
print(info.discoveryIndices); // [0, 1, 2, 3]
print(info.lowLinks); // [0, 0, 0, 3]
print(info.resultCount); // 2