What is a Spanning Tree?

A spanning tree of the graph, G is a tree that spans G (that is, it includes every vertex of G ) and is a subgraph of G (every edge in the tree belongs to G ) given an undirected and connected graph G =(V,E).


Minimum Spanning Tree

The cost of the spanning tree is the total of all the weights of the tree's edges. There may be several spanning trees. The spanning tree with the lowest cost among all spanning trees is known as the minimal spanning tree. There may also be a large number of minimal spanning trees.

The minimum spanning tree has direct use in network architecture. It's utilized in algorithms that try to solve the travelling salesman issue, the multi-terminal minimal cut problem, and the minimum-cost weighted perfect matching.


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

The Kruskal Algorithm

Kruskal's Algorithm constructs the spanning tree by gradually adding edges to a developing spanning tree. Kruskal's method takes a greedy approach, finding the edge with the least weight in each iteration and adding it to the developing spanning tree.

Implementation

#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;
}


Prim’s Algorithm

The Greedy technique is also used by Prim's Algorithm to discover the least spanning tree. Prim's Algorithm grows a spanning tree from a starting point. Unlike Kruskal's edge, we add a vertex to Prim's developing spanning tree.

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;
}