Skip to content

steinerTree ​

steinerTree(edges, vertexCount, terminals) conecta los terminales solicitados mediante caminos no dirigidos ponderados y devuelve las aristas seleccionadas. Una lista de terminales vacía devuelve un array vacío; los terminales inalcanzables también devuelven un array vacío.

Tanto edges como steinerTreeInfo también aceptan Graph<N, i32>; agregue ambas direcciones de cada arista no dirigida al Graph.

FirmaRetornoComplejidad
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); // 2

Resultado de estudio ​

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