prim
prim(adjacency, origin) grows a minimum spanning tree from origin with a priority queue. For disconnected inputs it returns the component reachable from origin.
Both adjacency and primInfo also accept Graph<N, i32>; add both directions of each undirected edge to a Graph.
| Signature | Returns | Complexity |
|---|---|---|
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); // 2Study result
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