Things to be discussed here.

• Spanning Tree
• Minimum Spanning Tree ( MST )
• Kruskal’s Algorithm
• Practice Problem

Before discussing MST, we will first take look into “Spanning Tree”.

## Spanning Tree

A spanning tree of a graph is a graph that consists of all nodes of the graph and some of the edges of the graph so that there exists a path between any two nodes. Spanning trees are connected and acyclic like a tree. For example, take a look at the below picture, where (a) is the original graph (b) and (c) are some of its spanning trees.

Observation:

• If we denote graph by G = (V, E ) then G’ = ( V, E’ ) will be spanning tree if and only if E’ = V – 1 so that the graph formed be acyclic and connected. E’ is a subset of E and if E=V-1 then E’ = E.
• There will at least 1 spanning tree for the given graph.

## Minimum Spanning Tree

Minimum spanning trees are those spanning trees whose edge weight is a minimum of all spanning trees. For example, let us suppose we a graph with 5 spanning trees having the sum of edge weights 9,9,10,11,12 then, in this case, we will get 2 MST’s

• More than two MSTs are possible when all the edge weights are not distinct.
• If all the edge weights are distinct then we will get a Unique MST.

Similarly, if we take a maximum weight spanning tree then we will get Maximum Spanning Tree.Now we will be exploring two algorithms to find MST.

• Kruskal’s Algorithm
• Prim’s Algorithm ( To be discussed in the next article )

Both of these are the greedy algorithms and the same algorithm can be used for finding Maximum Spanning Tree by taking maximum edge weights instead of the minimum. So let us start with Kruskal’s Algorithm.

## Kruskal’s Algorithm

Kruskal’s Algorithm implements the greedy technique to builds the spanning tree by adding edges one by one into a growing spanning tree. In each iteration, it finds an edge that has the least weight and adds it to the growing spanning tree.

## Algorithm Steps:

• Store the graph as an edge list.
• Sort the graph edges with respect to their weights.
• Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.
• Only add those edge which doesn’t form a cycle, i.e. edges which connect only disconnected components.

Okay, now the question arises that how we will check if the 2 vertices are connected or not? The simple answer would be to traverse the graph and check whether the we can reach from the first node to the second node using DFS.

• But this will increase the time complexity as for every edge we traverse the whole graph.
• For one traversal DFS cost is O( V + E ).
• So the total cost would be O( E*( V + E ) ).

Okay, cool. we will not be using this algorithm for checking cycle as it takes lots of time, which we don’t have. The best solution to check the presence of the cycle is to use “Disjoint Sets”.

## Disjoint Sets ( Union Find ):

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

• Using Disjoint Sets in Kruskal’s algorithm we get a time complexity of O ( ElogV )

Please go through the below explanatory video from Youtube to understand Disjoint Sets and it’s an application in Kruskal’s Algorithm.

## Implementation in C++

``````#include <bits/stdc++.h>
using namespace std;

int find(int parent[], int u) {
if (parent[u] != u) find(parent, parent[u]);
return parent[u];
}

void unite(int parent[], int u, int v) {
int p = find(parent, u);
int q = find(parent, v);
parent[p] = parent[q];
}

int kruskals(vector<tuple<int, int, int> > edges, int n, int m) {
vector<tuple<int, int, int> > output;
int parent[n + 1];
for (int i = 1; i <= n; i++) parent[i] = i;
for (int i = 0; i < m; i++) {
int w, u, v;
tie(w, u, v) = edges[i];
// check if selected edge is creating cycle or not.
if (find(parent, u) != find(parent, v)) {
output.push_back(edges[i]);
unite(parent, u, v);
}
}

// printing the edges.
int minCost = 0;
cout << "Connected final edges in MST\n";
for (int i = 0; i < n - 1; i++) {
int w, u, v;
tie(w, u, v) = output[i];
minCost += w;
cout << u << "--" << v << " = " << w << "\n";
}
cout << "The Minimum Cost: ";
return minCost;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m;
cin >> n >> m;
vector<tuple<int, int, int> > edges;
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
edges.push_back(make_tuple(
w, u, v));  // storing in this way as it will be easy to sort.
}
sort(edges.begin(), edges.end());
cout << kruskals(edges, n, m) << "\n";
return 0;
}``````

Input:

``````7 9
1 2 10
2 4 40
3 4 25
1 3 15
4 5 35
2 5 30
5 6 10
5 7 8
6 7 9``````

Output:

``````Connected final edges in MST
5--7 = 8
6--7 = 9
1--2 = 10
1--3 = 15
3--4 = 25
2--5 = 30
The Minimum Cost: 97``````

## Applications:

• In electronic circuit design to minimize the wire length.
• To find routing path in networks
• Airplane network routes.
• Network Design etc.

## Practice Problem

That’s all for this article, in the next session we will be discussing Prim’s Algorithm and problems related to it and for now practice problems ( If you stuck then do comment Question Number for Solution and your approach so that other programmer or we can help you).

If you have some content OR material related to this OR there is an error then do share them through the comment section for which we will be thankful to you.

Thank You
With 💙 by Learn DSA