Kruskal algorithm in c++
Kruskal algorithm in C++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Edge {
public:
int src, dest, weight;
};
class Graph {
public:
int V, E;
vector<Edge> edges;
Graph(int v, int e) {
V = v;
E = e;
edges.resize(e);
}
int find(vector<int>& parent, int i) {
if (parent[i] == -1)
return i;
return find(parent, parent[i]);
}
void Union(vector<int>& parent, int x, int y) {
int xset = find(parent, x);
int yset = find(parent, y);
parent[xset] = yset;
}
void kruskalMST() {
vector<Edge> result(V);
int e = 0;
int i = 0;
sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
return a.weight < b.weight;
});
vector<int> parent(V, -1);
while (e < V - 1 && i < E) {
Edge next_edge = edges[i++];
int x = find(parent, next_edge.src);
int y = find(parent, next_edge.dest);
if (x != y) {
result[e++] = next_edge;
Union(parent, x, y);
}
}
for (i = 0; i < e; ++i)
cout << result[i].src << " - " << result[i].dest << endl;
}
};
int main() {
int V = 4;
int E = 5;
Graph graph(V, E);
// add edge 0-1
graph.edges[0].src = 0;
graph.edges[0].dest = 1;
graph.edges[0].weight = 10;
// add edge 0-2
graph.edges[1].src = 0;
graph.edges[1].dest = 2;
graph.edges[1].weight = 6;
// add edge 0-3
graph.edges[2].src = 0;
graph.edges[2].dest = 3;
graph.edges[2].weight = 5;
// add edge 1-3
graph.edges[3].src = 1;
graph.edges[3].dest = 3;
graph.edges[3].weight = 15;
// add edge 2-3
graph.edges[4].src = 2;
graph.edges[4].dest = 3;
graph.edges[4].weight = 4;
graph.kruskalMST();
return 0;
}
The Kruskal algorithm is used to find the minimum spanning tree for a connected, undirected graph. In this implementation, we create a class Edge
to represent edges in the graph, and a class Graph
to represent the graph itself. The kruskalMST
method in the Graph
class implements the Kruskal algorithm. We use the find
method to find the subset of an element, and the Union
method to perform union operation of two subsets. In the main
function, we create a sample graph with 4 vertices and 5 edges, and then call the kruskalMST
method to find the minimum spanning tree.