Minimum Spanning Tree

Definition:

For a given graph, spanning tree refers to a subgraph which is a fully connected tree(remember tree is a graph in which there exists only a single path between any pair or vertices). If we assign weights to all the edges of the graph, then the spanning tree with minimum weight of all the possible spanning trees is the minimum spanning tree.

Kruskal's Algorithm:

Let us first define an empty graph called MST. Sort all the edges of the input graph in non-decreasing order of edge weights. Iterate through all the edges of the graph in order. For each edge we need to check if adding that particular edge will introduce cycle in MST. If not then add the edge to MST otherwise reject it. We can use Disjoint-Set data structure to check for cycles.

class UnionFind{
    int * links; 
    int * ranks;
    int numberOfNodes;

    public:
    int find(int node){
        int parent = node;
        if(links[node] != node){
            parent = find(links[node]);
            links[node] = parent;
        }
        
        return parent; 
    }
    
    bool connect(int a, int b){
        int p1 = find(a);
        int p2 = find(b);
        
        if(p1 == p2)
            return false;
        
        int p, c;
        
        if(ranks[p1] < ranks[p2]){
            p = p1, c = p2;
        }
        else{
            p = p2, c = p1;
        }
        
        links[c] = p;
        ranks[p] += ranks[c];
        
        return true;
    }
    
    UnionFind(int n): numberOfNodes(n){
        if(n == 0)
            return;
        
        links = new int[n];
        ranks = new int[n];
        
        for(int i = 0; i < n; i ++){
            links[i] = i, ranks[i] = 1;
        }
    }
};

int main() {
    
    int n, m;
    cin>>n>>m;
    
    unordered_map<int, list<pair<int, int>>> lookup;
    lookup.rehash(n);
    vector<int> distances(m);
    
    for(int i = 0; i < m; i ++){
        int x, y, d;
        cin>>x>>y>>d;
        
        distances[i] = d;
        lookup[d].push_back(make_pair(x, y));
    }
    
    priority_queue<int, vector<int>, greater<int>> pq(distances.begin(), distances.end());
    UnionFind uf(n);
        
    while(pq.empty() == false){
        int d = pq.top();
        unordered_map<int, list<pair<int, int>>>::iterator itr = lookup.find(d);
        if(itr != lookup.end() && itr->second.size() != 0){
            pair<int, int> point = *(itr->second.begin());
            itr->second.pop_front();
            
            if(uf.connect(point.first - 1, point.second -1)){
                //Add the vertex pair to the OUTPUT;
            }            
        }
        
        pq.pop();
    }
    
    return 0;
}