Given a undirected, connected and weighted graph, construct a minimum spanning tree out of it.

A **Minimum Spanning Tree** is a spanning tree of a connected, undirected graph. It connects all the vertices together with the minimal total weighting for its edges.

For example, consider above graph. Its minimum spanning tree will be below tree with exactly N-1 edges where N is number of vertices in the graph and sum of weights of edges is as minimum as possible.

**Prerequisite:** __Union-Find Algorithm for Cycle Detection in undirected graph__

We can use** Kruskal’s Minimum Spanning Tree** algorithm which is a greedy algorithm to find a minimum spanning tree for a connected weighted graph. Kruskal’s Algorithm works by finding a subset of the edges from the given graph covering every vertex present in the graph such that they forms a tree (called MST) and sum of weights of edges is as minimum as possible.

Let G = (V, E) be the given graph. Initially our MST contains only vertices of given graph with no edges. In other words, initially MST has V connected components with each vertex acting as one connected component. The goal is to add minimum weight edges to our MST such that we are left with single connected component that comprises all the vertices of graph. Below is the complete algorithm –

Sort all edges in the graph G in the order of their increasing weights;

repeat V-1 times // as MST contains V-1 edges

{

Select the next edge with minimum weight from the graph G;

if (no cycle is formed by adding the edge in MST i.e. the edge connects two

different connected components in MST)

add the edge to MST;

}

Let’s illustrate this by taking example of above graph. Initially our MST consists of only the vertices of given graph with no edges. We start by considering smallest weighted edge 0-3 having weight 5. As no cycle is formed, we include it in our MST.

We next consider smallest weighted edge 2-4 also having weight 5. As no cycle is formed, we include it in our MST.

We next consider smallest weighted edge 3-5 having weight 6. As no cycle is formed, we include it in our MST.

We next consider smallest weighted edge 0-1 having weight 7. As no cycle is formed, we include it in our MST.

We next consider smallest weighted edge 1-4 also having weight 7. As no cycle is formed, we include it in our MST.

We next consider smallest weighted edge 5-4 having weight 8. But including this edge in MST will result in a cycle 0-1-4-5-3-0, so we discard it.

We next consider smallest weighted edge 1-2 also having weight 8. But including this edge in MST will result in a cycle 1-2-4-1, so we discard it.

We next consider smallest weighted edge 3-1 also having weight 9. But including this edge in MST will result in a cycle 0-1-3-0, so we discard it.

Finally we consider next smallest weighted edge 4-6 also having weight 9. As no cycle is formed, we include it in our MST.

MST is now connected (contaning V-1 edges). So we discard all remaining edges.

Below is the pseudocode of Kruskal’s Algorithm as per wikipedia. It uses disjoint-set data structure.

KRUSKAL(graph G)

MST = {}

for each vertex v belonging G.V:

MAKE-SET(v)

for each (u, v) in G.E ordered by weight(u, v), increasing:

if FIND-SET(u) != FIND-SET(v):

add {(u, v)} to set MST

UNION(u, v)

return MST

Please note that if the graph is not connected, then Kruskal’s Algorithm finds a **Minimum Spanning Forest** which is a minimum spanning tree for each connected component of the graph.

**C++ implementation –**

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 |
#include <bits/stdc++.h> using namespace std; // Number of vertices in the graph #define N 7 // data structure to store graph edges struct Edge { int src, dest, weight; }; // class to represent a disjoint set class DisjointSet { unordered_map<int, int> parent; public: // perform MakeSet operation void makeSet() { // create N disjoint sets (one for each vertex) for (int i = 0; i < N; i++) parent[i] = i; } // Find the root of the set in which element k belongs int Find(int k) { // if k is root if (parent[k] == k) return k; // recurse for parent until we find root return Find(parent[k]); } // Perform Union of two subsets void Union(int a, int b) { // find root of the sets in which elements // x and y belongs int x = Find(a); int y = Find(b); parent[x] = y; } }; // construct MST using Kruskal's algorithm vector<Edge> KruskalAlgo(vector<Edge> edges) { // stores edges present in MST vector<Edge> MST; // initialize DisjointSet class DisjointSet ds; // create singleton set for each element of universe ds.makeSet(); // MST contains exactly V-1 edges while (MST.size() != N - 1) { // consider next edge with minimum weight from the graph Edge next_edge = edges.back(); edges.pop_back(); // find root of the sets to which two endpoint // vertices of next_edge belongs int x = ds.Find(next_edge.src); int y = ds.Find(next_edge.dest); // if both endpoints have different parents, they belong to // different connected components and can be included in MST if (x != y) { MST.push_back(next_edge); ds.Union(x, y); } } return MST; } // Comparison object to be used to order the Edges struct compare { inline bool operator() (const Edge& a, const Edge& b) { return (a.weight > b.weight); } }; // main function int main() { // vector of graph edges as per above diagram. vector<Edge> edges = { // (u, v, w) tiplet represent undirected edge from // vertex u to vertex v having weight w { 0, 1, 7 }, { 1, 2, 8 }, { 0, 3, 5 }, { 1, 3, 9 }, { 1, 4, 7 }, { 2, 4, 5 }, { 3, 4, 15 }, { 3, 5, 6 }, { 4, 5, 8 }, { 4, 6, 9 }, { 5, 6, 11 } }; // sort edges by increasing weight sort(edges.begin(), edges.end(), compare()); // construct graph vector<Edge> e = KruskalAlgo(edges); for (Edge edge: e) cout << "(" << edge.src << ", " << edge.dest << ", " << edge.weight << ")" << endl; return 0; } |

**Output: **

(2, 4, 5)

(0, 3, 5)

(3, 5, 6)

(1, 4, 7)

(0, 1, 7)

(4, 6, 9)

**References:**

https://en.wikipedia.org/wiki/Kruskal%27s_algorithm

http://lcm.csa.iisc.ernet.in/dsa/node184.html

**Thanks for reading.**

Please use ideone or C++ Shell or any other online compiler link to post code in comments.

Like us? Please spread the word and help us grow. Happy coding 🙂