Kruskal's Algorithm

Kruskal's Algorithm is another greedy algorithm used to find the minimum spanning tree (MST) of a connected, undirected graph. It works by building the MST from the ground up, starting with no edges and adding edges in increasing order of weight.

How Kruskal's Algorithm Works

1. Initialization:   - Sort all edges in increasing order of weight.   - Create a set to track vertices included in the MST (initially empty).

2. Selecting Edges:   - While the MST set does not include all vertices:    - Select the minimum-weight edge that connects two vertices in different sets.    - Add the selected edge to the MST.    - Union the two sets that the selected edge connects.

3. Completion:   - Continue this process until all vertices are included in the MST.

Key Features

• Greedy Approach: Kruskal's Algorithm makes locally optimal choices to build a globally optimal solution.

• Minimum Spanning Tree: It finds the MST, ensuring the least possible total edge weight to connect all vertices.

Efficiency

• Time Complexity: The time complexity of Kruskal's Algorithm depends on the data structures used for the graph. With a priority queue, it typically runs in O(E log E) time, where E is the number of edges.

• Space Complexity: The space complexity depends on the data structures used. In the worst case, it can be O(E + V).

Applications

• Network Design: Kruskal's Algorithm is widely used in network design, including laying down minimum-length electrical wires or connecting a set of houses with minimal cost.

• Image Segmentation: It can be applied in image processing for image segmentation, where it partitions an image into regions.

• Cluster Analysis: Kruskal's Algorithm is used for clustering data points in various applications, such as data mining and spatial analysis.

Limitations

• Must Be Connected: Kruskal's Algorithm requires the graph to be connected. If the graph has disconnected components, it needs to be run separately on each component.

• Doesn't Work for Directed Graphs: It is designed for undirected graphs. For directed graphs, other algorithms like Prim's Algorithm may be used.

• Sensitivity to Edge Weights: The algorithm's performance can vary based on the choice of edge weights. Different edge weight assignments can result in different minimum spanning trees.

Kruskal's Algorithm Implementation in JavaScript

Here's an example of Kruskal's Algorithm implemented in JavaScript:

class Graph {
  constructor() {
    this.vertices = [];
    this.edges = [];
  }
 
  addVertex(vertex) {
    this.vertices.push(vertex);
  }
 
  addEdge(vertex1, vertex2, weight) {
    this.edges.push({ vertex1, vertex2, weight });
  }
 
  kruskalMST() {
    const mst = [];
    const subsets = new Array(this.vertices.length).fill(null).map((_, i) => i);
 
    // Sort edges in increasing order of weight
    this.edges.sort((a, b) => a.weight - b.weight);
 
    for (const edge of this.edges) {
      const set1 = subsets[edge.vertex1];
      const set2 = subsets[edge.vertex2];
 
      // If the two vertices are in different sets, add the edge to the MST and union the two sets
      if (set1 !== set2) {
        mst.push(edge);
        subsets[edge.vertex1] = subsets[edge.vertex2] = set1;
      }
    }
 
    return mst;
  }
}
 
// Example usage
const graph = new Graph();
const vertices = ["A", "B", "C", "D", "E"];
vertices.forEach((vertex) => graph.addVertex(vertex));
 
graph.addEdge("A", "B", 2);
graph.addEdge("A", "C", 3);
graph.addEdge("B", "C", 1);
graph.addEdge("B", "D", 1);
graph.addEdge("C", "D", 1);
graph.addEdge("C", "E", 4);
graph.addEdge("D", "E", 2);
 
const mst = graph.kruskalMST();
console.log("Minimum Spanning Tree (MST):", mst);