findCutVertices
findCutVertices(graph) devuelve los vértices cuya eliminación desconecta un grafo no dirigido. Acepta una lista de adyacencia o Graph<N, W>.
| Firma | Retorno | Complejidad |
|---|---|---|
findCutVertices(graph: usize[][]) | usize[] | O(V + E) |
findCutVertices(graph: Graph<N, W>) | usize[] | O(V + E) |
La lista debe contener entradas simétricas. Cada vértice aparece una sola vez.
Ejemplo
tyrus
import { findCutVertices } from "tyrus:algorithm";
const cuts: usize[] = findCutVertices([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(cuts.length); // 1Resultado para estudio
findCutVerticesInfo devuelve FindCutVerticesInfo, con vértices de corte copiados y métricas low-link compartidas.
tyrus
interface FindCutVerticesInfo {
examinedEdgeCount: usize;
discoveryIndices: usize[];
lowLinks: usize[];
resultCount: usize;
cutVertices: usize[];
}tyrus
import { ConnectivityInfo, FindCutVerticesInfo, findCutVerticesInfo } from "tyrus:algorithm";
const info: FindCutVerticesInfo = findCutVerticesInfo([[1, 2], [0, 2, 3], [0, 1], [1]]);
print(info.cutVertices); // [1]
print(info.examinedEdgeCount); // 8
print(info.discoveryIndices); // [0, 1, 2, 3]
print(info.lowLinks); // [0, 0, 0, 3]
print(info.resultCount); // 1