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
| Sintaxis | Descripción |
|---|---|
centroidDecomposition(adj: usize[][]) | Descomponer el árbol adj en un árbol centroid |
Métodos
| Método | Firma | Devuelve | Descripción |
|---|---|---|---|
parentOf | (v: usize) | usize? | Padre en el árbol centroid de v; ausente para la raíz centroid global |
depth | (v: usize) | usize | Profundidad de v en el árbol centroid (raíz con profundidad 0) |
Complejidad
| Operación | Complejidad Temporal |
|---|---|
| construcción | O(n), cálculo iterativo de tamaños por componente y búsqueda del centroid |
parentOf, depth | O(1) |
| memoria | O(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)); // 2camino 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)); // 0importació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