Minimum Spanning Tree

Description:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible.

There are quite a few use cases for minimum spanning trees. One example would be a telecommunications company which is trying to lay out cables in new neighborhood.

Example:

Note

Idea:

Prim’s method. Time Complexity of the above program is O(V^2). If the input graph is represented using adjacency list, then the time complexity of Prim’s algorithm can be reduced to O(E log V) with the help of binary heap.

Code:

#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <stack>
#include <queue>
#include <utility>
#include <memory>
#include <cmath>

using namespace std;

// A structure to represent a node in adjacency list
struct AdjListNode
{
    AdjListNode(int d, int w): dest(d), weight(w) {}
    int dest;
    int weight;
};

// A structure to represent a graph. A graph is an array of adjacency lists.
// Size of array will be V (number of vertices in graph)
class Graph{
public:
    Graph() = delete;
    Graph(int n): V(n), edges(n) {}

    void addEdge(int src, int dest, int weight){
        // src to dest Edge
        edges[src].emplace_back(AdjListNode(dest, weight));
        // Un-directed graph, set dest to src Edge too
        edges[dest].emplace_back(AdjListNode(src, weight));    
    }    

    const int V;
    vector<vector<AdjListNode>> edges;
};

int minDistUnvisited(const vector<pair<int,int>>& dist, const unordered_set<int>& visited){
    int min_dist=INT_MAX;
    int min_ind;
    for(int i=0; i<dist.size(); ++i){
        if(visited.find(i)==visited.end() && dist[i].second<=min_dist){
            min_dist = dist[i].second;
            min_ind = i;
        }
    }
    return min_ind;
}

vector<pair<int,int>> minSpanning(const Graph & graph, int root){
    unordered_set<int> visited;
    vector<pair<int,int>> min_edge(graph.V);
    for(int i=0; i<graph.V; i++){
        min_edge[i].first = i;
        min_edge[i].second = INT_MAX;
    }

    min_edge[root].second = 0;
    int next_v = root;

    while(visited.size()!=graph.V && min_edge[next_v].second!=INT_MAX){
        visited.insert(next_v);

        for(int i=0; i<graph.edges[next_v].size(); ++i){
            int neighbor = graph.edges[next_v][i].dest;
            int neighbor_weight = graph.edges[next_v][i].weight;
            // if neighbor is unvisited, update
            if(visited.find(neighbor)==visited.end()){
                if(min_edge[neighbor].second > neighbor_weight){
                    min_edge[neighbor].second = neighbor_weight;
                    min_edge[neighbor].first = next_v;
                }                
            }

        }
        next_v = minDistUnvisited(min_edge, visited);
    }

    return min_edge;
}


int main(){
    // create the graph given in above fugure
    int V = 9;
    // struct Graph* graph = createGraph(V);
    Graph graph(V);
    graph.addEdge(0, 1, 4);
    graph.addEdge(0, 7, 8);
    graph.addEdge(1, 2, 8);
    graph.addEdge(1, 7, 11);
    graph.addEdge(2, 3, 7);
    graph.addEdge(2, 8, 2);
    graph.addEdge(2, 5, 4);
    graph.addEdge(3, 4, 9);
    graph.addEdge(3, 5, 14);
    graph.addEdge(4, 5, 10);
    graph.addEdge(5, 6, 2);
    graph.addEdge(6, 7, 1);
    graph.addEdge(6, 8, 6);
    graph.addEdge(7, 8, 7);

    int root=0;
    vector<pair<int,int>> edges = minSpanning(graph, root);

    int weight_sum=0;
    cout<<"parent  node  weight"<<endl;
    for(int i=0; i<V; i++){
        if(i!=root){
            weight_sum += edges[i].second;
            cout<<i<<' '<<edges[i].first<<' '<<edges[i].second<<endl;
        }
    }
    cout<<"total weights: "<<weight_sum<<endl;

}