Minimal Spanning Tree

A minimal spanning tree (MST) is a subset of the edges of a weighted, connected graph that connects all the vertices with the minimum possible total edge weight. It is a fundamental concept in graph theory and finds applications in various domains, including network design, clustering, and optimization problems. The most commonly used algorithms to find the minimal spanning tree are Kruskal's algorithm and Prim's algorithm.

Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm that finds the minimal spanning tree by iteratively adding edges with the smallest weight that do not create a cycle.

Algorithm:

1. Sort all the edges of the graph in non-decreasing order of their weights.

2. Create an empty set to hold the minimal spanning tree.

3. Iterate over the sorted edges, and for each edge:

- If adding the edge does not create a cycle in the minimal spanning tree set, add it to the set.

- Otherwise, discard the edge.

4. Continue this process until the minimal spanning tree set contains (V-1) edges, where V is the number of vertices in the graph.

Code:

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// Structure to represent an edge

struct Edge {

`    `int src, dest, weight;

};

// Structure to represent a subset for union-find

struct Subset {

`    `int parent;

`    `int rank;

};

// Find operation of union-find

int find(vector<Subset>& subsets, int i) {

`    `if (subsets[i].parent != i)

`        `subsets[i].parent = find(subsets, subsets[i].parent);

`    `return subsets[i].parent;

}

// Union operation of union-find

void unionSet(vector<Subset>& subsets, int x, int y) {

`    `int xroot = find(subsets, x);

`    `int yroot = find(subsets, y);

`    `if (subsets[xroot].rank < subsets[yroot].rank)

`        `subsets[xroot].parent = yroot;

`    `else if (subsets[xroot].rank > subsets[yroot].rank)

`        `subsets[yroot].parent = xroot;

`    `else {

`        `subsets[yroot].parent = xroot;

`        `subsets[xroot].rank++;

`    `}

}

// Comparator function to sort edges in ascending order of weight

bool compareEdges(const Edge& a, const Edge& b) {

`    `return a.weight < b.weight;

}

// Kruskal's algorithm implementation

vector<Edge> kruskalMST(vector<Edge>& edges, int V) {

`    `// Sort edges in ascending order of weight

`    `sort(edges.begin(), edges.end(), compareEdges);

`    `vector<Edge> mst;  // Minimum Spanning Tree

`    `vector<Subset> subsets(V);

`    `for (int i = 0; i < V; ++i) {

`        `subsets[i].parent = i;

`        `subsets[i].rank = 0;

`    `}

`    `int edgeCount = 0;

`    `int index = 0;

`    `while (edgeCount < V - 1) {

`        `Edge nextEdge = edges[index++];

`        `int x = find(subsets, nextEdge.src);

`        `int y = find(subsets, nextEdge.dest);

`        `if (x != y) {

`            `mst.push\_back(nextEdge);

`            `unionSet(subsets, x, y);

`            `++edgeCount;

`        `}

`    `}

`    `return mst;

}

int main() {

`    `int V = 4;  // Number of vertices in the graph

`    `vector<Edge> edges = {

`        `{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}

`    `};

`    `vector<Edge> mst = kruskalMST(edges, V);

`    `cout << "Edges in the Minimum Spanning Tree:\n";

`    `for (const auto& edge : mst) {

`        `cout << edge.src << " -- " << edge.dest << "   Weight: " << edge.weight << endl;

`    `}

`    `return 0;

}