kruskal.ts

import { DisjointSet } from '../data_structures/disjoint_set/disjoint_set';

/**
 * @function kruskal
 * @description Compute a minimum spanning forest of a weighted undirected graph
 * @Complexity_Analysis
 * Time complexity: O(Elog(V))
 * Space Complexity: O(V)
 * @param {Edge[]} edges - The edges of the graph
 * @param {number} num_vertices - The number of vertices in the graph
 * @return {Edge[], number} - [The edges of the minimum spanning tree, the sum of the weights of the edges in the tree]
 * @see https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
 */
export const kruskal = (edges: Edge[], num_vertices: number): [Edge[], number] => {
  let cost = 0;
  let minimum_spanning_tree = [];

  // Use a disjoint set to quickly join sets and find if vertices live in different sets
  let sets = new DisjointSet(num_vertices);

  // Sort the edges in ascending order by weight so that we can greedily add cheaper edges to the tree
  edges.sort((a, b) => a.weight - b.weight);

  for (let edge of edges) {
    if (sets.find(edge.a) !== sets.find(edge.b)) {
      // Node A and B live in different sets. Add edge(a, b) to the tree and join the nodes' sets together.
      minimum_spanning_tree.push(edge);
      cost += edge.weight;
      sets.join(edge.a, edge.b);
    }
  }

  return [minimum_spanning_tree, cost];
}

export class Edge {
  a: number = 0;
  b: number = 0;
  weight: number = 0;
  constructor(a: number, b: number, weight: number) {
    this.a = a;
    this.b = b;
    this.weight = weight;
  }
}