minimum-spanning-tree

minimum-spanning-tree.md

MINIMUM SPANNING TREE NOTES

ST(Spanning Tree) is a tree like subgraph of a connected, undirected graph that include all the vertices of the graph. In simple words, It is a tree like structure (hence no cycle) where the edges are the subset of graph and vertices are the exact set of original graph.

MST is excatly same like ST but with one more constraint of having minimum weight sum of edges.

Properties

• Number of vertices in MST and graph will be same (as we said exact set of original graph)
• number of edges in MST will be 1 less than, first, number of vertices in MST and second, number of vertices in graph.
• It should not be disconnected.
• No cycle
• can be more than MST for single graph

NOTES: Since the MST is a optimiztion problem it is going to have only a unique solution. That means for a given graph we'll have only one Minimum Cost Spanning tree.

NOTE 2 : we can have more than one MST structure for a same graph but the Cost of all that MST will be same and unque.

For Example for this given graph:

One of the spanning tree out of many is:

and the MST is:

you can try all possible spanning tree and can find that no spanning tree will have sum less than 16.

TIP: How to find the MST of a graph from given graph on paper without code.

• Write all the nodes as it is from the graph without any edge included.
• Now choose the minimum edge weight from original graph and connet the nodes which you drawn in first step
• do it util all the points are not gets connected.

Algorithms for finding MST

• Kruskal's Algorithm
• Prim's Algorithm
• Boruvka's Algorithm

Prim's Algorithm:

In it's simplest these are the steps for prims algorithm:

• Draw all the vertices without edges
• start from minimum edge and connect a both Vertices.
• Now only considers the edges which can be reached from the already made MST at that point and take the minimum out of them and add the edge to the current MST.
• Do the same untill you can able to connect all the vertices, i.e. V - 1 edges

Use cases

• This can be required to find the Minimum Cost of the Minimum Spanning tree.
• Or you may be asked to provide the Minimum Spanning Tree(MST) itself.

First One:

class Solution {
public:
    int spanningTree(int V, vector<vector<int>>& edges) {
        // Adjacency list: node -> {neighbor, weight}
        vector<vector<pair<int, int>>> adj(V);
        
        for (auto &e : edges) {
            int u = e[0], v = e[1], wt = e[2];
            adj[u].push_back({v, wt});
            adj[v].push_back({u, wt});
        }

        vector<bool> inMST(V, false);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

        long long mstCost = 0;
        int nodesTaken = 0;

        // Start from node 0
        pq.push({0, 0});

        while (!pq.empty() && nodesTaken < V) {
            auto [wt, node] = pq.top();
            pq.pop();

            if (inMST[node]) continue;

            inMST[node] = true;
            mstCost += wt;
            nodesTaken++;

            for (auto &[next, edgeWt] : adj[node]) {
                if (!inMST[next]) {
                    pq.push({edgeWt, next});
                }
            }
        }

        // If graph is disconnected, MST doesn't exist
        if (nodesTaken != V) return -1;

        return mstCost;
    }
};

This is the lazy Prim's Algorithm, It doesn't account if the wrong edges are getting pushed in the queue at the first moment, but check them later with the visited condition. You can implement the Eager one and that can be a good optimiztion if asked in interviews. Go and google it. I am not discussing it anyway here.

Second One:

There are two way, you either use the complex data structure and get the MST edges or use the simple data structure with some tweaks in the code to get the MST edges. here are the both.

class Solution {
public:
    int spanningTree(int V, vector<vector<int>>& edges, vector<pair<int,int>>& mstEdges) {
        // Build adjacency list
        vector<vector<pair<int,int>>> adj(V);
        for (auto &e : edges) {
            int u = e[0], v = e[1], w = e[2];
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        vector<int> visited(V, 0);
        // complex queue but simple in logic wise.
        priority_queue<pair<int, pair<int,int>>,  vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> pq;

        // Start from node 0, put a dummy edge from -1 to 0 with weight 0
        pq.push({0, {-1, 0}});

        long long minCost = 0;

        while (!pq.empty()) {
            auto [wt, nodes] = pq.top(); pq.pop();
            int u = nodes.first;  // parent
            int v = nodes.second; // current node

            if (visited[v]) continue;
            visited[v] = 1;

            minCost += wt;
            if (u != -1) mstEdges.push_back({u, v}); // ignore the first dummy edge

            // Push all edges from v
            for (auto &[nbr, w] : adj[v]) {
                if (!visited[nbr]) {
                    pq.push({w, {v, nbr}});
                }
            }
        }

        return minCost;
    }
};

class Solution {
public:
    // Returns MST weight and stores edges in mstEdges
    int spanningTree(int V, vector<vector<int>>& edges, vector<pair<int,int>>& mstEdges) {
        // Build adjacency list
        vector<vector<pair<int,int>>> adj(V);
        for (auto &e : edges) {
            int u = e[0], v = e[1], w = e[2];
            adj[u].push_back({v, w});
            adj[v].push_back({u, w});
        }

        vector<int> visited(V, 0);
        vector<int> parent(V, -1); // Track parent of each node in MST
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;

        long long minCost = 0;
        pq.push({0, 0}); // Start from node 0

        while (!pq.empty()) {
            auto [wt, node] = pq.top();
            pq.pop();

            if (visited[node]) continue;

            visited[node] = 1;
            minCost += wt;

            if (parent[node] != -1) {
                mstEdges.push_back({parent[node], node});
            }

            for (auto &[nbr, w] : adj[node]) {
                if (!visited[nbr]) {
                    pq.push({w, nbr});
                    // Track potential parent: only set if not yet set
                    if (parent[nbr] == -1) parent[nbr] = node;
                }
            }
        }

        return minCost;
    }
};

Kruskal's Algorithm:

This is another algorithm to find the MST of the graph. It used DSU/ Union-Find algorithm to find the MST. The core logic is given in the steps below:

• You start with drawing all the vertices.
• Now you pick up the Minimum edge and connect the vertices.
• You do the 2nd step V - 1 time and now you don't care if the next edge you are trying to add is coming from the already build mst or not.
• But you don't connect the edge if it result in cycle in your MST. (This is the part Union Find helps us with: If two vertices are in the same set then they are creating cycle and hence we ignore that edge in MST creation).

This is Kruskal in the Nutshell. The good thing is that Kruskal works in the Disconnected graph also. It gives us a MST Forest not MST.

Bro add the algorithm for this too here hehehehehehehe.

Here you go with the code also. why to wait when you can do it Right now.

// User function Template for C++

class DSU {
    public: 
    vector<pair<int, int>> parent;
    
    DSU(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = {i, 1}; // initially, parent is self, size is 1
        }
    }
    
    // union and find are the two operation we need to implement
    int find(int v) {
        if (parent[v].first == v){
            return parent[v].first;
        }
        return parent[v].first = find(parent[v].first);
    }
    
    bool unite(int u, int v) {
        // find the size of the subtree and add parent of smaller to large one.
        int uRoot = find(u);
        int vRoot = find(v);
        
        if (uRoot == vRoot) {
            return false;
        }
        
        if (parent[uRoot].second < parent[vRoot].second) {
            parent[uRoot].first = vRoot;
            parent[vRoot].second += parent[uRoot].second;
        }
        else {
            parent[vRoot].first = uRoot;
            parent[uRoot].second += parent[vRoot].second;
        }
        
        return true;
    }
};

class Solution {
  public:
  
    int kruskalsMST(int V, vector<vector<int>> &edges) {
        // code here
        
        sort(edges.begin(), edges.end(), [](const vector<int> &edge1, const vector<int> &edge2) -> bool {
            return edge1[2] < edge2[2];
        });
        int minCost = 0;
        DSU dsu(V);
        
        for (vector<int> edge: edges){ 
            if (dsu.unite(edge[0], edge[1])) {
                minCost += edge[2];
            }
        }
        
        return minCost;
        
    }
};