Skip to content

prim ​

prim(adjacency, origin) construye un árbol de expansión mínima desde origin usando una cola de prioridad. En entradas desconectadas, devuelve el componente alcanzable desde origin.

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

FirmaRetornoComplejidad
prim(adjacency: [usize, i32][][], origin: usize)[usize, usize, i32][]O((V + E) log V)
tyrus
import { prim } from "tyrus:algorithm";

const tree: [usize, usize, i32][] = prim([[[1, 2]], [[0, 2], [2, 1]], [[0, 2], [1, 1]]], 0);
print(tree.length); // 2

Resultado de estudio ​

tyrus
interface PrimInfo {
    edges: [usize, usize, i32][];
    totalWeight: i32;
    componentCount: usize;
    examinedEdgeCount: usize;
    acceptedEdgeCount: usize;
    heapPushCount: usize;
    heapPopCount: usize;
    keyUpdateCount: usize;
}
tyrus
import { PrimInfo, SpanningTreeInfo, primInfo } from "tyrus:algorithm";

const info: PrimInfo = primInfo([[[1, 4], [2, 2]], [[0, 4], [2, 1], [3, 5]], [[0, 2], [1, 1], [3, 8], [4, 10]], [[1, 5], [2, 8], [4, 2]], [[2, 10], [3, 2]]], 0);
print(info.edges); // [[0, 2, 2], [2, 1, 1], [1, 3, 5], [3, 4, 2]]
print(info.totalWeight); // 10
print(info.componentCount); // 1
print(info.examinedEdgeCount); // 12
print(info.acceptedEdgeCount); // 4
print(info.heapPushCount); // 7
print(info.heapPopCount); // 7
print(info.keyUpdateCount); // 7