Kruskal

Introduction:

This algorithm finds an MST(minimum spanning tree) from a connected undirected graph. Remember that this algorithm fails sometimes in case of directed graph since kruskal's algorithm finds a cylce when there is none.

Problem Statement:

Find minimum spanning tree of an undirected graph G.

Algorithm

Code :

    #include <bits/stdc++.h>
    using namespace std;
    
    #define adjacency_list map<int, vector<pair<int, int>>>
    #define mp make_pair
    #define INF INT_MAX
    
    typedef struct edge
    {
        int u;
        int v;
        int w;
    } Edge;
    
    typedef struct graph
    {
        adjacency_list adj;
    
        int num_edges;
        int num_vertices;
        Edge *edge;
    } graph;
    
    int edge_compare(const void *a, const void *b)
    {
        Edge *c = (Edge *)a;
        Edge *d = (Edge *)b;
        return c->w > d->w; // return 1 i.e., swap if greater
    }
    
    int find_parent(map<int, int> &parent, int u)
    {
        if (parent[u] != u)
        {
            parent[u] = find_parent(parent, parent[u]);
        }
        return parent[u];
    }
    
    void Union(map<int, int> &rank, map<int, int> &parent, int rootu, int rootv)
    {
        if (rank[rootu] < rank[rootv])
        {
            parent[rootu] = rootv;
        }
        else if (rank[rootv] < rank[rootu])
        {
            parent[rootv] = rootu;
        }
        else
        {
            parent[rootv] = rootu;
            rank[rootu]++;
        }
    }
    
    void kruskal(graph G)
    {
        qsort(G.edge, G.num_edges, sizeof(Edge), edge_compare);
    
        // cout<<"kruskal-"<<G.num_edges<<"\n";
        map<int, int> parent;
        map<int, int> rank;
    
        for (int i = 0; i < G.num_vertices; i++)
        {
            parent[i] = i;
            // rank[i] = 0; // not needed since we are using map
        }
    
        int sum = 0, cnt = 0, i = 0;
        for (int i = 0; i < G.num_edges; i++)
        {
            int rootu = find_parent(parent, G.edge[i].u);
            int rootv = find_parent(parent, G.edge[i].v);
            if (rootu != rootv)
            {
                Union(rank, parent, rootu, rootv);
                cnt++;
                // this edge is part of MST
                sum += G.edge[i].w;
                cout << G.edge[i].u << " " << G.edge[i].v << " " << G.edge[i].w << "\n";
    
                if (cnt >= G.num_vertices - 1)
                {
                    break;
                }
            }
        }
        cout << sum << "\n";
    }
    
    int main()
    {
        // undirected graph
    
        graph G; // u - {{v1,w1}, {v2, w2}, .... {vk,wk}}
        cin >> G.num_vertices;
        cin >> G.num_edges;
        G.edge = new Edge[G.num_edges];
        int u, v, w;
        for (int i = 0; i < G.num_edges; i++)
        {
            cin >> G.edge[i].u >> G.edge[i].v >> G.edge[i].w;
        }
    
        kruskal(G);
        // cout << "\n";
    }

Complexity Analysis :

Time complexity : \(O(|E|log|E|+|E|log|V|)\) where \(|E|log|E|\) is for sorting and \(log|V|\) is for Union-find algorithm.

Time complexity ≈ \(O(|E|log|V|)\) or \(O(|E|log|E|)\) since \(|E|\) ≤ \(|V|^2\)

Kruskal

Introduction:

Problem Statement:

Algorithm

Code :

Complexity Analysis :

video resources

web resources

book resources