> For the complete documentation index, see [llms.txt](https://soumyajit4419.gitbook.io/ds-algo/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://soumyajit4419.gitbook.io/ds-algo/graph/graph-algorithms/4.kruskal-mst.md).

# 4.Kruskal (MST)

## Algorithm

```cpp
// Initialize result
mst_weight = 0

// Create V single item sets
for each vertex v
	parent[v] = v;
	rank[v] = 0;

Sort all edges into non decreasing 
order by weight w

for each (u, v) taken from the sorted list  E
    do if FIND-SET(u) != FIND-SET(v)
        print edge(u, v)
        mst_weight += weight of edge(u, v)
        UNION(u, v)
```

## Code: 

```cpp
#include <bits/stdc++.h>

using namespace std;

int findPar(vector<int> &parent, int node)
{

    if (parent[node] == -1)
    {
        return node;
    }

    parent[node] = findPar(parent, parent[node]);
    return parent[node];
}

void uni(vector<int> &parent, vector<int> &rank, int a, int b)
{
    int parA = findPar(parent, a);
    int parB = findPar(parent, b);

    if (parA != parB)
    {

        if (rank[parA] > rank[parB])
        {
            parent[parB] = parA;
        }
        else if (rank[parB] > rank[parA])
        {
            parent[parA] = parB;
        }
        else
        {
            parent[parA] = parB;
            rank[parB]++;
        }
    }
    return;
}

int main()
{
    int n, m;
    cin >> n >> m;

    vector< pair<int, pair<int, int>> > v;
    vector<int> parent(n + 1, -1);
    vector<int> rank(n + 1, 0);
    for (int k = 1; k <= m; k++)
    {
        int a, b, w;
        cin >> a >> b >> w;
        v.push_back({w, {a, b}});
    }

    sort(v.begin(), v.end());
    int minWeight = 0;
    for (auto itr = v.begin(); itr != v.end(); itr++)
    {
        pair<int, int> p = itr->second;
        int x = p.first;
        int y = p.second;

        int pa = findPar(parent,x);
        int py = findPar(parent,y);

        if (pa != py)
        {
            uni(parent, rank, x, y);
            minWeight = minWeight + itr->first;
        }

    }

    cout << minWeight;

    return 0;
}
```

**Time Complexity: O(E logE) or O(E logV)**. **Sorting of edges takes O(E Log E) time**. After sorting, we iterate through all edges and apply **find-union** algorithm. The **find and union operations** can take atmost **O(LogV)** time. So overall complexity is **O(E Log E + E Log V) time.**