Similarly to Prim's algorithm, Kruskal's algorithm is also a greedy algorithm that finds the MST for a connected weighted undirected graph.
Kruskal's algorithm is given as follows:
const kruskal = graph => { const { length } = graph; const parent = []; let ne = 0; let a; let b; let u; let v; const cost = initializeCost(graph); // {1} while (ne < length - 1) { // {2} for (let i = 0, min = INF; i < length; i++) { // {3} for (let j = 0; j < length; j++) { if (cost[i][j] < min) { min = cost[i][j]; a = u = i; b = v = j; } } } u = find(u, parent); // {4} v = find(v, parent); // {5} if (union(u, v, parent)) { // {6} ne++; } cost[a][b] = cost[b][a] = INF; // {7} } return parent;};
The following is a description of how the algorithm ...