Skip to content

centroidDecomposition ​

centroidDecomposition(adj: usize[][]): Centroid constrói a decomposição centroid sobre a árvore não direcionada descrita pela lista de adjacência adj, onde adj[v] guarda os vizinhos do vértice v. A Centroid retornada é um handle de propriedade do chamador de tyrus:algorithm; todo vértice da árvore de entrada vira um nó da árvore centroid, e remover um centroid divide cada componente em componentes filhos com profundidade de no máximo metade do seu tamanho. Ela expõe parentOf(v), que devolve o pai na árvore centroid de v como usize? (a raiz centroid global não tem pai), e depth(v), a profundidade de v na árvore centroid (raiz com profundidade 0).

Construção ​

SintaxeDescrição
centroidDecomposition(adj: usize[][])Decompor a árvore adj em uma árvore centroid

Métodos ​

MétodoAssinaturaRetornaDescrição
parentOf(v: usize)usize?Pai na árvore centroid de v; ausente para a raiz centroid global
depth(v: usize)usizeProfundidade de v na árvore centroid (raiz com profundidade 0)

Complexidade ​

OperaçãoComplexidade Temporal
construçãoO(n), cálculo iterativo de tamanhos por componente e busca do centroid
parentOf, depthO(1)
memóriaO(n)

Exemplos ​

árvore balanceada ​

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

caminho 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

importação 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