findBridges
findBridges(graph) devuelve cada arista no dirigida cuya eliminación aumenta el número de componentes conexos. Acepta una lista de adyacencia o Graph<N, W>.
| Firma | Retorno | Complejidad |
|---|---|---|
findBridges(graph: usize[][]) | [usize, usize][] | O(V + E) |
findBridges(graph: Graph<N, W>) | [usize, usize][] | O(V + E) |
La lista debe contener entradas simétricas. Cada resultado es un par de índices de vértices.
Ejemplo
tyrus
import { findBridges } from "tyrus:algorithm";
const bridges: [usize, usize][] = findBridges([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(bridges.length); // 1Resultado para estudio
tyrus
interface FindBridgesInfo {
examinedEdgeCount: usize;
discoveryIndices: usize[];
lowLinks: usize[];
resultCount: usize;
bridges: [usize, usize][];
}tyrus
import { ConnectivityInfo, FindBridgesInfo, findBridgesInfo } from "tyrus:algorithm";
const info: FindBridgesInfo = findBridgesInfo([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(info.bridges); // [[1, 3]]
print(info.examinedEdgeCount); // 8
print(info.discoveryIndices); // [0, 1, 2, 3]
print(info.lowLinks); // [0, 0, 0, 3]
print(info.resultCount); // 1