Minimum Spanning Tree Algorithms

Algorithm Steps

1. Sort all edges in non-decreasing order of weight
2. Initialize a disjoint-set data structure with each vertex in its own set
3. Iterate through the sorted edges:
   • If including the current edge doesn't form a cycle (i.e., the endpoints are in different sets), add it to the MST
   • Union the sets containing the endpoints of the included edge
4. Continue until n-1 edges have been added to the MST

Implementation

class DisjointSet {
  constructor(n) {
    this.parent = Array(n).fill().map((_, i) => i);
    this.rank = Array(n).fill(0);
  }
  
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path compression
    }
    return this.parent[x];
  }
  
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    
    if (rootX === rootY) return false;
    
    // Union by rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }
    
    return true;
  }
}

function kruskalMST(graph) {
  const vertices = graph.vertices;
  const edges = graph.edges;
  
  // Sort edges by weight
  edges.sort((a, b) => a.weight - b.weight);
  
  const disjointSet = new DisjointSet(vertices.length);
  const mst = [];
  
  for (const edge of edges) {
    const { src, dest, weight } = edge;
    
    // Check if adding this edge creates a cycle
    if (disjointSet.union(src, dest)) {
      mst.push(edge);
      
      // Break early if we have n-1 edges (a spanning tree)
      if (mst.length === vertices.length - 1) break;
    }
  }
  
  return mst;
}

Algorithm Steps

1. Start with any vertex as the initial MST
2. Maintain two sets: vertices in the MST and vertices not yet included
3. Maintain a priority queue of edges connecting the MST to vertices outside the MST
4. In each step:
   • Select the edge with minimum weight that connects a vertex in the MST to a vertex outside
   • Add the selected edge to the MST and the new vertex to the MST set
   • Update the priority queue with new edges from the newly added vertex
5. Continue until all vertices are included in the MST

Implementation

function primMST(graph) {
  const vertices = graph.vertices.length;
  const adjList = graph.adjList;
  
  // Track vertices included in MST
  const inMST = Array(vertices).fill(false);
  
  // Key values used to pick minimum weight edge
  const key = Array(vertices).fill(Infinity);
  
  // Parent array to store MST
  const parent = Array(vertices).fill(-1);
  
  // Start with first vertex
  key[0] = 0;
  
  for (let count = 0; count < vertices - 1; count++) {
    // Pick the minimum key vertex not yet included in MST
    const u = minKey(key, inMST, vertices);
    
    // Add the picked vertex to the MST
    inMST[u] = true;
    
    // Update key and parent of adjacent vertices
    for (const [v, weight] of adjList[u]) {
      if (!inMST[v] && weight < key[v]) {
        parent[v] = u;
        key[v] = weight;
      }
    }
  }
  
  // Construct MST from parent array
  const mst = [];
  for (let i = 1; i < vertices; i++) {
    mst.push({
      src: parent[i],
      dest: i,
      weight: key[i]
    });
  }
  
  return mst;
}

function minKey(key, inMST, vertices) {
  let min = Infinity, minIndex = -1;
  
  for (let v = 0; v < vertices; v++) {
    if (!inMST[v] && key[v] < min) {
      min = key[v];
      minIndex = v;
    }
  }
  
  return minIndex;
}