What is a Spanning Tree?

Given an undirected and connected graph , a spanning tree of the graph may be a tree that spans (that is, it includes every vertex of ) and may be a subgraph of (every edge up the tree belongs to )

What is a Minimum Spanning Tree?

The cost of the spanning tree is that the sum of the weights of all the sides within the tree. There are often many spanning trees. Minimum spanning tree is that the spanning tree where the value is minimum among all the spanning trees. There can also be many minimum spanning trees.

Minimum spanning tree has direct application within the design of networks. it’s utilized in algorithms approximating the traveling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching. Other practical applications are:

Cluster Analysis

Handwriting recognition

Image segmentation

There are two famous algorithms for locating the Minimum Spanning Tree:

Kruskal’s Algorithm

Kruskal’s Algorithm builds the spanning tree by adding edges one by one into a growing spanning tree. Kruskal’s algorithm follows greedy approach as in each iteration it finds a foothold which has least weight and add it to the growing spanning tree.

Algorithm Steps:

Sort the graph edges with reference to their weights.

Start adding edges to the MST from the sting with the littlest weight until the sting of the most important weight.

Only add edges which does not form a cycle , edges which connect only disconnected components.

So now the question is the way to check if vertices are connected or not ?

This could be done using DFS which starts from the primary vertex, then check if the second vertex is visited or not. But DFS will make time complexity large because it has an order of where is that the number of vertices, is that the number of edges. therefore the best solution is “Disjoint Sets”:

Disjoint sets are sets whose intersection is that the empty set so it means they do not have any element in common.

In Kruskal’s algorithm, at each iteration we’ll select the sting with rock bottom weight. So, we’ll start with rock bottom weighted edge first i.e., the sides with weight 1. then we’ll select the second lowest weighted edge i.e., edge with weight 2. Notice these two edges are totally disjoint. Now, subsequent edge are going to be the third lowest weighted edge i.e., edge with weight 3, which connects the 2 disjoint pieces of the graph. Now, we aren’t allowed to select the sting with weight 4, which will create a cycle and that we can’t have any cycles. So we’ll select the fifth lowest weighted edge i.e., edge with weight 5. Now the opposite two edges will create cycles so we’ll ignore them. within the end, we find yourself with a minimum spanning tree with total cost 11 ( = 1 + 2 + 3 + 5).In Prim’s Algorithm, we’ll start with an arbitrary node (it doesn’t matter which one) and mark it. In each iteration we’ll mark a replacement vertex that’s adjacent to the one that we’ve already marked. As a greedy algorithm, Prim’s algorithm will select the most cost effective edge and mark the vertex. So we’ll simply choose the sting with weight 1. within the next iteration we’ve three options, edges with weight 2, 3 and 4. So, we’ll select the sting with weight 2 and mark the vertex. Now again we’ve three options, edges with weight 3, 4 and 5. But we can’t choose edge with weight 3 because it is creating a cycle. So we’ll select the sting with weight 4 and that we find yourself with the minimum spanning tree of total cost 7 ( = 1 + 2 +4).

#include <iostream>

#include <vector>

#include <utility>

#include <algorithm>

using namespace std;

const int MAX = 1e4 + 5;

int id[MAX], nodes, edges;

pair <long long, pair<int, int> > p[MAX];

void initialize()

{

    for(int i = 0;i < MAX;++i)

        id[i] = i;

}

int root(int x)

{

    while(id[x] != x)

    {

        id[x] = id[id[x]];

        x = id[x];

    }

    return x;

}

void union1(int x, int y)

{

    int p = root(x);

    int q = root(y);

    id[p] = id[q];

}

long long kruskal(pair<long long, pair<int, int> > p[])

{

    int x, y;

   long long cost, minimumCost = 0;

    for(int i = 0;i < edges;++i)

    {

        // Selecting edges one by one in increasing order from the beginning

        x = p[i].second.first;

        y = p[i].second.second;

        cost = p[i].first;

        // Check if the selected edge is creating a cycle or not

        if(root(x) != root(y))

        {

            minimumCost += cost;

            union1(x, y);

        }    

    }

    return minimumCost;

}

int main()

{

    int x, y;

    long long weight, cost, minimumCost;

    initialize();

    cin >> nodes >> edges;

    for(int i = 0;i < edges;++i)

    {

        cin >> x >> y >> weight;

        p[i] = make_pair(weight, make_pair(x, y));

    }

    // Sort the edges in the ascending order

    sort(p, p + edges);

    minimumCost = kruskal(p);

    cout << minimumCost << endl;

    return 0;

}

Time Complexity:

In Kruskal’s algorithm, most time consuming operation is sorting because the entire complexity of the Disjoint-Set operations are going to be , which is that the overall Time Complexity of the algorithm.

Prim’s Algorithm

Prim’s Algorithm also use Greedy approach to seek out the minimum spanning tree. In Prim’s Algorithm we grow the spanning tree from a starting position. Unlike a foothold in Kruskal’s, we add vertex to the growing spanning tree in Prim’s.

Algorithm Steps:

Maintain two disjoint sets of vertices. One containing vertices that are within the growing spanning tree and other that aren’t within the growing spanning tree.

Select the most cost effective vertex that’s connected to the growing spanning tree and isn’t within the growing spanning tree and add it into the growing spanning tree. this will be done using Priority Queues. Insert the vertices, that are connected to growing spanning tree, into the Priority Queue.

Check for cycles. to try to to that, mark the nodes which are already selected and insert only those nodes within the Priority Queue that aren’t marked.

Consider the instance below:

In Prim’s Algorithm, we’ll start with an arbitrary node (it doesn’t matter which one) and mark it. In each iteration we’ll mark a replacement vertex that’s adjacent to the one that we’ve already marked. As a greedy algorithm, Prim’s algorithm will select the most cost effective edge and mark the vertex. So we’ll simply choose the sting with weight 1. within the next iteration we’ve three options, edges with weight 2, 3 and 4. So, we’ll select the sting with weight 2 and mark the vertex. Now again we’ve three options, edges with weight 3, 4 and 5. But we can’t choose edge with weight 3 because it is creating a cycle. So we’ll select the sting with weight 4 and that we find yourself with the minimum spanning tree of total cost 7 ( = 1 + 2 +4).

Implementation:

#include <iostream>

#include <vector>

#include <queue>

#include <functional>

#include <utility>

using namespace std;

const int MAX = 1e4 + 5;

typedef pair<long long, int> PII;

bool marked[MAX];

vector <PII> adj[MAX];

long long prim(int x)

{

    priority_queue<PII, vector<PII>, greater<PII> > Q;

    int y;

    long long minimumCost = 0;

    PII p;

    Q.push(make_pair(0, x));

    while(!Q.empty())

    {

        // Select the edge with minimum weight

        p = Q.top();

        Q.pop();

        x = p.second;

        // Checking for cycle

        if(marked[x] == true)

            continue;

        minimumCost += p.first;

        marked[x] = true;

        for(int i = 0;i < adj[x].size();++i)

        {

            y = adj[x][i].second;

            if(marked[y] == false)

                Q.push(adj[x][i]);

        }

    }

    return minimumCost;

}

int main()

{

    int nodes, edges, x, y;

    long long weight, minimumCost;

    cin >> nodes >> edges;

    for(int i = 0;i < edges;++i)

    {

        cin >> x >> y >> weight;

        adj[x].push_back(make_pair(weight, y));

        adj[y].push_back(make_pair(weight, x));

    }

    // Selecting 1 as the starting node

    minimumCost = prim(1);

    cout << minimumCost << endl;

    return 0;

}