Minimum Spanning Tree

📌 Table of Contents

1. Properties

2. Kruskal (Sparse Graph)


// Kruskal's Algorithm for Minimum Spanning Tree
#include <bits/stdc++.h>
#define pp push_back
using namespace std;
using ll = long long;
const int maxn = 1e5+5;
int n,m,dsu[maxn],sz[maxn],cnt=0;
ll ans;
struct node
{
    int u, v, w;
};
vector <node> e;

bool cmp(node x, node y)
{
    return x.w<y.w;
}

// Disjoint Set Union (DSU) functions
int find_set(int u)
{
    if(dsu[u]==u)   return u;
    else            return dsu[u]=find_set(dsu[u]);
}

void unite(int u, int v, int w)
{
    int id=find_set(u), id1=find_set(v);
    if(id!=id1)
    {
        if(sz[id]>=sz[id1])
        {
            sz[id]+=sz[id1];
            dsu[id1]=id;
        }
        else
        {
            sz[id1]+=sz[id];
            dsu[id]=id1;
        }
        ans+=w;
        ++cnt;
    }
}

void input()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        dsu[i]=i;
        sz[i]=1;
    }
    for(int i=1,u,v,w;i<=m;++i)
    {
        cin>>u>>v>>w;
        node tmp;
        tmp.u=u;
        tmp.v=v;
        tmp.w=w;
        e.pp(tmp);
    }
    sort(all(e),cmp);
    for(node i : e) unite(i.u,i.v,i.w);
    if(cnt==n-1)    cout<<ans;
    else            cout<<-1;
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    return 0;
}

        

3. Prim (Dense Graph)


// Prim's Algorithm for Minimum Spanning Tree            
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pp push_back
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using pii = pair <int,int>;
const char el ='\n';
const char sp = ' ';
const int maxn = 1e5+5, inf = 1e9+1;
int n,m,d[maxn];
bool mark [maxn];
vector <pii> adj[maxn];
ll ans;

void Prim()
{
    d[1]=0;
    int cnt = 0;
    while(cnt<n)
    {
        int mn = inf, id;
        for(int i=1;i<=n;++i){
            if(!mark[i] && d[i]<mn){
                mn = d[i];
                id = i;
            }
        }
        ++cnt;
        mark[id] = true;
        ans +=mn;
        for(pii i : adj[id])    d[i.ff] = min(d[i.ff],i.ss);
    }
    cout<<ans;
}

void input()
{
    cin>>n>>m;
    fill(d,d+n+1,inf);
    for(int i=1,u,v,w;i<=m;++i)
    {
        cin>>u>>v>>w;
        adj[u].pp({v,w});
        adj[v].pp({u,w});
    }
    Prim();
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    input();
    return 0;
}