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
| Sintaxe | Descrição |
|---|---|
centroidDecomposition(adj: usize[][]) | Decompor a árvore adj em uma árvore centroid |
Métodos
| Método | Assinatura | Retorna | Descrição |
|---|---|---|---|
parentOf | (v: usize) | usize? | Pai na árvore centroid de v; ausente para a raiz centroid global |
depth | (v: usize) | usize | Profundidade de v na árvore centroid (raiz com profundidade 0) |
Complexidade
| Operação | Complexidade Temporal |
|---|---|
| construção | O(n), cálculo iterativo de tamanhos por componente e busca do centroid |
parentOf, depth | O(1) |
| memória | O(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)); // 2caminho 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)); // 0importaçã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