steinerTree
steinerTree(edges, vertexCount, terminals) conecta os terminais solicitados por caminhos não direcionados ponderados e retorna as arestas selecionadas. Uma lista de terminais vazia retorna um array vazio; terminais inalcançáveis também retornam um array vazio.
Tanto edges quanto steinerTreeInfo também aceitam Graph<N, i32>; adicione as duas direções de cada aresta não direcionada ao Graph.
| Assinatura | Retorno | Complexidade |
|---|---|---|
steinerTree(edges: [usize, usize, i32][], vertexCount: usize, terminals: usize[]) | [usize, usize, i32][] | O(T · (E + V) log V + E log V) |
tyrus
import { steinerTree } from "tyrus:algorithm";
const tree: [usize, usize, i32][] = steinerTree([[0, 1, 2], [1, 2, 1]], 3, [0, 2]);
print(tree.length); // 2Resultado de estudo
tyrus
interface SteinerTreeInfo {
edges: [usize, usize, i32][];
totalWeight: i32;
terminals: usize[];
evaluatedSubsetCount: usize;
vertexCount: usize;
maxTerminalCount: usize;
withinTerminalLimit: bool;
}tyrus
import { SteinerTreeInfo, steinerTreeInfo } from "tyrus:algorithm";
const info: SteinerTreeInfo = steinerTreeInfo([[0, 1, 4], [0, 2, 2], [1, 2, 1], [1, 3, 5], [2, 3, 8], [2, 4, 10], [3, 4, 2]], 5, [0, 4]);
print(info.edges); // [[0, 2, 2], [1, 2, 1], [1, 3, 5], [3, 4, 2]]
print(info.totalWeight); // 10
print(info.terminals); // [0, 4]
print(info.evaluatedSubsetCount); // 3
print(info.vertexCount); // 5
print(info.maxTerminalCount); // 20
print(info.withinTerminalLimit); // true