Skip to content

kruskal ​

kruskal(edges, vertexCount) ordena las aristas ponderadas y selecciona cada arista que une dos componentes distintos. Devuelve un bosque de expansión mínima cuando la entrada está desconectada.

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

FirmaRetornoComplejidad
kruskal(edges: [usize, usize, i32][], vertexCount: usize)[usize, usize, i32][]O(E log E)
tyrus
import { kruskal } from "tyrus:algorithm";

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

Resultado de estudio ​

tyrus
interface KruskalInfo {
    edges: [usize, usize, i32][];
    totalWeight: i32;
    componentCount: usize;
    examinedEdgeCount: usize;
    acceptedEdgeCount: usize;
    unionAttemptCount: usize;
    successfulUnionCount: usize;
    sortedEdgeExaminationCount: usize;
}
tyrus
import { KruskalInfo, SpanningTreeInfo, kruskalInfo } from "tyrus:algorithm";

const info: KruskalInfo = kruskalInfo([[0, 1, 4], [0, 2, 2], [1, 2, 1], [1, 3, 5], [3, 4, 2]], 5);
print(info.edges); // [[1, 2, 1], [0, 2, 2], [3, 4, 2], [1, 3, 5]]
print(info.totalWeight); // 10
print(info.componentCount); // 1
print(info.examinedEdgeCount); // 5
print(info.acceptedEdgeCount); // 4
print(info.unionAttemptCount); // 5
print(info.successfulUnionCount); // 4
print(info.sortedEdgeExaminationCount); // 5