🌉 Kruskal’s Algorithm – Complete In-Depth Explanation

**Kruskal’s Algorithm** is a **greedy algorithm** used to find the **Minimum Spanning Tree (MST)** of a weighted, **connected, and undirected graph**. The **MST** is a subset of the graph’s edges that connects all vertices with the **minimum total edge weight** and contains **no cycles**.

📌 Why Use Kruskal’s Algorithm?

• ✅ **Greedy approach ensures global optimization.**
• 📡 **Works well with sparse graphs (O(E log E) time complexity).**
• 🔍 **Finds the Minimum Spanning Tree efficiently.**
• 🌍 **Used in network design, clustering, and image segmentation.**

📌 Understanding the Minimum Spanning Tree (MST)

A **Minimum Spanning Tree (MST)** is a **subset of a graph’s edges** that connects all vertices together with the **minimum total edge weight** and **without forming cycles**.

🔹 **Properties of an MST**

• ✅ The MST has **V - 1 edges** (where V is the number of vertices).
• 📉 The MST has the **minimum total edge weight**.
• 🔄 The MST contains **no cycles**.
• 🌐 The MST **may not be unique** (multiple MSTs may exist).

🛠 Steps in Kruskal’s Algorithm

📌 **Step 1: Sort All Edges by Weight**

Sort all edges in **ascending order** based on their weight.

📌 **Step 2: Initialize the MST**

Start with an empty set of edges in the MST.

📌 **Step 3: Add the Minimum Edge Without Forming a Cycle**

Use the **Disjoint Set Union (DSU)** (Union-Find) data structure to check for cycles.

📌 **Step 4: Stop When MST Has (V - 1) Edges**

Once the MST has **V - 1 edges**, the algorithm stops.

📜 Example Graph

                    Graph:
                       2
                    A-----B
                    |     |
                  1 |     | 3
                    |     |
                    C-----D
                       4
            
                    Sorted Edges by Weight: 
                    (C-A, 1), (A-B, 2), (B-D, 3), (C-D, 4)
            
                    MST Output:
                       2
                    A-----B
                    |      
                  1 |      
                    |      
                    C      
                

📌 Implementation of Kruskal’s Algorithm (O(E log E))

                struct Edge {
                    int src, dest, weight;
                };
            
                struct Graph {
                    int V, E;
                    vector edges;
                };
            
                struct DisjointSet {
                    vector parent, rank;
            
                    DisjointSet(int n) {
                        parent.resize(n);
                        rank.resize(n, 0);
                        for (int i = 0; i < n; i++) parent[i] = i;
                    }
            
                    int find(int x) {
                        if (parent[x] != x) parent[x] = find(parent[x]);
                        return parent[x];
                    }
            
                    void unite(int x, int y) {
                        int rootX = find(x), rootY = find(y);
                        if (rootX != rootY) {
                            if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
                            else if (rank[rootX] < rank[rootY]) parent[rootX] = rootY;
                            else {
                                parent[rootY] = rootX;
                                rank[rootX]++;
                            }
                        }
                    }
                };
            
                void kruskal(Graph &graph) {
                    sort(graph.edges.begin(), graph.edges.end(), [](Edge a, Edge b) {
                        return a.weight < b.weight;
                    });
            
                    DisjointSet ds(graph.V);
                    vector mst;
                    int mstCost = 0;
            
                    for (Edge e : graph.edges) {
                        if (ds.find(e.src) != ds.find(e.dest)) {
                            ds.unite(e.src, e.dest);
                            mst.push_back(e);
                            mstCost += e.weight;
                        }
                    }
            
                    cout << "Minimum Spanning Tree Cost: " << mstCost << endl;
                    for (Edge e : mst) {
                        cout << e.src << " -- " << e.dest << " == " << e.weight << endl;
                    }
                }
                

⏳ Time Complexity Analysis

🌍 Real-World Applications of Kruskal’s Algorithm

• 📡 **Network Design** – Laying down **minimum-cost communication cables.**
• 🚗 **Road Systems** – Designing **minimum-cost road networks.**
• 🔗 **Computer Clustering** – Connecting **servers with minimal latency.**
• 🛰 **Electric Grid Design** – Optimizing **power transmission networks.**

🔗 Next Topics

• 🌲 Prim’s Algorithm (MST)
• 📡 Graph Algorithms
• 🔗 Disjoint Set Union (DSU)