Last Updated on March 29, 2022 by Ria Pathak
CONCEPTS USED:
Greedy algorithm, Kruskal’s algorithm.
DIFFICULTY LEVEL:
Hard
PROBLEM STATEMENT(SIMPLIFIED):
Karan’s came home after a long time and he wants to visit all the relatives. The total number of Karan’s’s relatives is N and all of them are living in different cities. He can begin from any relative and visits all of them one after another. He doesn’t know the cost of visiting all relative, so he asks you to find the minimum cost of visiting all relatives.
Note: solve this problem with the help of kruskal’s Algorithm.
See original problem statement here
For Example :
5 5
1 5 3
1 2 1
2 3 4
3 4 5
4 5 2
10
Karan starts from vertex (relative) 3,then goes to 2 (0+4), then 1 (0+4+1) ,then 5 (0+4+1+3) and then finally to relative 4 (0+4+1+3+2).
Therefore,the total minimum cost incurred is 10.OBSERVATION:
The idea is simple, to visit all relatives by spending minimum cost means all vertices must be connected. So the two disjoint subsets of vertices must be connected to make a Spanning Tree. And they must be connected with the minimum weight edge to make it a Minimum Spanning Tree.
This is what Kruskal’s algorithm says.
SOLVING APPROACH:
Visiting all the relatives by spending minimum cost is very similar to finding the minimum spanning tree for the given graph(the path diagram between each).
Kruskal’s algorithm is a minimum-spanning-tree algorithm which finds an edge of the least possible weight that connects any two trees in the forest.[1] It is a greedy algorithm in graph theory as it finds a minimum spanning tree for a connected weighted graph adding increasing cost arcs at each step.[1] This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. If the graph is not connected, then it finds a minimum spanning forest (a minimum spanning tree for each connected component).
Follow these steps:
-
Sort all the edges in non-decreasing order of their weight.
-
Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
-
Repeat step 2 until there are (N-1) edges in the spanning tree.
SOLUTIONS:
#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
using namespace std;
const int MAX = 100001;
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;
}
import java.util.*;
import java.lang.*;
import java.io.*;
class Graph
{
class Edge implements Comparable<Edge>
{
int src, dest, weight;
public int compareTo(Edge compareEdge)
{
return this.weight-compareEdge.weight;
}
};
class subset
{
int parent, rank;
};
int V, E;
Edge edge[];
Graph(int v, int e)
{
V = v;
E = e;
edge = new Edge[E];
for (int i=0; i<e; ++i)
edge[i] = new Edge();
}
int find(subset subsets[], int i)
{
if (subsets[i].parent != i)
subsets[i].parent = find(subsets, subsets[i].parent);
return subsets[i].parent;
}
void Union(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++;
}
}
void KruskalMST()
{
Edge result[] = new Edge[V]; // Tnis will store the resultant MST
int e = 0;
int i = 0;
for (i=0; i<V; ++i)
result[i] = new Edge();
Arrays.sort(edge);
subset subsets[] = new subset[V];
for(i=0; i<V; ++i)
subsets[i]=new subset();
for (int v = 0; v < V; ++v)
{
subsets[v].parent = v;
subsets[v].rank = 0;
}
i = 0;
while (e < V - 1)
{
Edge next_edge = new Edge();
next_edge = edge[i++];
int x = find(subsets, next_edge.src);
int y = find(subsets, next_edge.dest);
if (x != y)
{
result[e++] = next_edge;
Union(subsets, x, y);
}
}
} /* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
}
}
MAX = 100001 id = [i for i in range(MAX)] def root(x): while id[x] != x: id[x] = id[id[x]] x = id[x] return x def union1(x, y): p = root(x) q = root(y) id[p] = id[q] def kruskal(p): minimumCost = 0 for i in range(edges): x = p[i][1][0] y = p[i][1][1] cost = p[i][0] if root(x) != root(y): minimumCost += cost union1(x, y) return minimumCost nodes, edges = map(int,input().split()) p = [] for i in range(edges): x, y, weight = map(int,input().split()) p.append([weight, [x, y]]) p.sort() minimumCost = kruskal(p) print(minimumCost)
[forminator_quiz id="1439"]
This article tried to discuss Greedy algorithm, Kruskal’s algorithm. Hope this blog helps you understand and solve the problem. To practice more problems on Greedy algorithm, Kruskal’s algorithm you can check out MYCODE | Competitive Programming.