Skip to content

findCutVertices ​

findCutVertices(graph) retorna vértices cuja remoção desconecta um grafo não direcionado. Aceita uma lista de adjacência ou Graph<N, W>.

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

A lista deve conter entradas simétricas. Cada vértice aparece uma única vez.

Exemplo ​

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

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

Resultado para estudo ​

findCutVerticesInfo retorna FindCutVerticesInfo, com os vértices de corte copiados e métricas low-link compartilhadas.

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