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.
| Firma | Retorno | Complejidad |
|---|---|---|
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); // 2Resultado 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