Kruskal’s Algorithm-2
// Simple C++ implementation for Kruskal's
// algorithm
//https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/
#include <bits/stdc++.h>
using namespace std;
#define V 5
int parent[V];
// Find set of vertex i
int find(int i)
{
while (parent[i] != i)
i = parent[i];
return i;
}
// Does union of i and j. It returns
// false if i and j are already in same
// set.
void union1(int i, int j)
{
int a = find(i);
int b = find(j);
parent[a] = b;
}
// Finds MST using Kruskal's algorithm
void kruskalMST(int cost[][V])
{
int mincost = 0; // Cost of min MST.
// Initialize sets of disjoint sets.
for (int i = 0; i < V; i++)
parent[i] = i;
// Include minimum weight edges one by one
int edge_count = 0;
while (edge_count < V - 1) {
int min = INT_MAX, a = -1, b = -1;
for (int i = 0; i < V; i++) {
for (int j = 0; j < V; j++) {
if (find(i) != find(j) && cost[i][j] < min) {
min = cost[i][j];
a = i;
b = j;
}
}
}
union1(a, b);
printf("Edge %d:(%d, %d) cost:%d \n",
edge_count++, a, b, min);
mincost += min;
}
printf("\n Minimum cost= %d \n", mincost);
}
// driver program to test above function
int main()
{
/* Let us create the following graph
2 3
(0)--(1)--(2)
| / \ |
6| 8/ \5 |7
| / \ |
(3)-------(4)
9 */
int cost[][V] = {
{ INT_MAX, 2, INT_MAX, 6, INT_MAX },
{ 2, INT_MAX, 3, 8, 5 },
{ INT_MAX, 3, INT_MAX, INT_MAX, 7 },
{ 6, 8, INT_MAX, INT_MAX, 9 },
{ INT_MAX, 5, 7, 9, INT_MAX },
};
// Print the solution
kruskalMST(cost);
return 0;
}
মন্তব্যসমূহ
একটি মন্তব্য পোস্ট করুন