Skip to content

centroidDecomposition ​

centroidDecomposition(adj: usize[][]): Centroid construye la descomposición centroid sobre el árbol no dirigido descrito por la lista de adyacencia adj, donde adj[v] guarda los vecinos del vértice v. La Centroid devuelta es un handle de propiedad del llamador de tyrus:algorithm; todo vértice del árbol de entrada se convierte en un nodo del árbol centroid, y eliminar un centroid divide cada componente en componentes hijos con profundidad de a lo sumo la mitad de su tamaño. Expone parentOf(v), que devuelve el padre en el árbol centroid de v como usize? (la raíz centroid global no tiene padre), y depth(v), la profundidad de v en el árbol centroid (raíz con profundidad 0).

Construcción ​

SintaxisDescripción
centroidDecomposition(adj: usize[][])Descomponer el árbol adj en un árbol centroid

Métodos ​

MétodoFirmaDevuelveDescripción
parentOf(v: usize)usize?Padre en el árbol centroid de v; ausente para la raíz centroid global
depth(v: usize)usizeProfundidad de v en el árbol centroid (raíz con profundidad 0)

Complejidad ​

OperaciónComplejidad Temporal
construcciónO(n), cálculo iterativo de tamaños por componente y búsqueda del centroid
parentOf, depthO(1)
memoriaO(n)

Ejemplos ​

árbol balanceado ​

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

const adj: usize[][] = [[1, 2], [0, 3, 4], [0, 5, 6], [1], [1], [2], [2]];
const ct = centroidDecomposition(adj);

print(ct.parentOf(0) ?? 0);  // 0 (no parent, global centroid)
print(ct.depth(0));  // 0
print(ct.parentOf(3) ?? 0);  // 1
print(ct.depth(3));  // 2
print(ct.parentOf(5) ?? 0);  // 2
print(ct.depth(5));  // 2

camino profundo ​

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

const path: usize[][] = [[1], [0, 2], [1, 3], [2, 4], [3, 5], [4]];
const ct = centroidDecomposition(path);

print(ct.parentOf(2) ?? 0);  // 0 (no parent, global centroid)
print(ct.depth(2));  // 0
print(ct.parentOf(0) ?? 0);  // 1
print(ct.depth(0));  // 2

único vértice ​

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

const single: usize[][] = [[]];
const ct = centroidDecomposition(single);

print(ct.parentOf(0) ?? 0);  // 0 (no parent)
print(ct.depth(0));  // 0

importación por namespace ​

tyrus
import * as alg from "tyrus:algorithm";

const ct = alg.centroidDecomposition([[1], [0, 2], [1]]);
print(ct.parentOf(1) ?? 0);  // 0 (no parent)
print(ct.depth(0));  // 1