biconnectedComponents
biconnectedComponents(graph) descompone un grafo no dirigido en componentes biconexos de aristas mediante un recorrido de bajo enlace. Acepta una lista de adyacencia o Graph<N, W>.
| Firma | Retorno | Complejidad |
|---|---|---|
biconnectedComponents(graph: usize[][]) | [usize, usize][][] | O(V + E) |
biconnectedComponents(graph: Graph<N, W>) | [usize, usize][][] | O(V + E) |
Cada array interno contiene las aristas de un componente como pares de vértices. Los puentes forman componentes unitarios.
Ejemplo
tyrus
import { biconnectedComponents } from "tyrus:algorithm";
const components: [usize, usize][][] = biconnectedComponents([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(components.length); // 2Resultado para estudio
biconnectedComponentsInfo devuelve BiconnectedComponentsInfo, con componentes copiados y métricas low-link compartidas.
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