Sunday, 26 February 2023
here's the implementation of Kruskal's algorithm in Python:
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal_mst(self):
result = []
i, e = 0, 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e += 1
result.append([u, v, w])
self.union(parent, rank, x, y)
return result
To use the Kruskal's algorithm implementation, you can create a new instance of the Graph class and add edges to it using the add_edge() method. Then, you can call the kruskal_mst() method to find the minimum spanning tree.
Here's an example usage:
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print(g.kruskal_mst())
This will output the following minimum spanning tree:
[[2, 3, 4], [0, 3, 5], [0, 1, 10]]
here's an implementation of Kruskal's algorithm in Java:
import java.util.*;
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge e) {
return this.weight - e.weight;
}
}
class Graph {
int V, E;
Edge[] edges;
Graph(int v, int e) {
V = v;
E = e;
edges = new Edge[E];
for (int i = 0; i < E; i++) {
edges[i] = new Edge();
}
}
int find(int[] parent, int i) {
if (parent[i] == i) {
return i;
}
return find(parent, parent[i]);
}
void union(int[] parent, int[] rank, int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot]) {
parent[xroot] = yroot;
} else if (rank[xroot] > rank[yroot]) {
parent[yroot] = xroot;
} else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
void kruskalMST() {
Edge[] result = new Edge[V];
int e = 0;
int i = 0;
for (i = 0; i < V; i++) {
result[i] = new Edge();
}
Arrays.sort(edges);
int[] parent = new int[V];
int[] rank = new int[V];
for (int j = 0; j < V; j++) {
parent[j] = j;
rank[j] = 0;
}
i = 0;
while (e < V - 1) {
Edge next_edge = new 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, rank, x, y);
}
}
System.out.println("Following are the edges in the constructed MST:");
for (i = 0; i < e; ++i)
System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
}
}
public class KruskalAlgorithm {
public static void main(String[] args) {
int V = 4;
int E = 5;
Graph graph = new Graph(V, E);
graph.edges[0].src = 0;
graph.edges[0].dest = 1;
graph.edges[0].weight = 10;
graph.edges[1].src = 0;
graph.edges[1].dest = 2;
graph.edges[1].weight = 6;
graph.edges[2].src = 0;
graph.edges[2].dest = 3;
graph.edges[2].weight = 5;
graph.edges[3].src = 1;
graph.edges[3].dest = 3;
graph.edges[3].weight = 15;
graph.edges[4].src = 2;
graph.edges[4].dest = 3;
graph.edges[4].weight = 4;
graph.kruskalMST();
}
}
import java.util.*;
class KruskalAlgorithm {
public static void main(String[] args) {
int vertices = 6;
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 4));
edges.add(new Edge(0, 2, 3));
edges.add(new Edge(1, 2, 1));
edges.add(new Edge(1, 3, 2));
edges.add(new Edge(2, 3, 4));
edges.add(new Edge(3, 4, 2));
edges.add(new Edge(4, 5, 6));
KruskalAlgorithm algorithm = new KruskalAlgorithm();
List<Edge> mst = algorithm.findMinimumSpanningTree(edges, vertices);
int totalWeight = 0;
for (Edge edge : mst) {
totalWeight += edge.weight;
System.out.println(edge.source + " - " + edge.destination + ": " + edge.weight);
}
System.out.println("Total weight of minimum spanning tree: " + totalWeight);
}
public List<Edge> findMinimumSpanningTree(List<Edge> edges, int vertices) {
List<Edge> minimumSpanningTree = new ArrayList<>();
// Sort edges in ascending order of weight
Collections.sort(edges, Comparator.comparingInt(o -> o.weight));
// Create a disjoint set for all vertices
DisjointSet disjointSet = new DisjointSet(vertices);
for (Edge edge : edges) {
int root1 = disjointSet.find(edge.source);
int root2 = disjointSet.find(edge.destination);
// If the roots are not the same, add the edge to the minimum spanning tree
if (root1 != root2) {
minimumSpanningTree.add(edge);
disjointSet.union(root1, root2);
}
}
return minimumSpanningTree;
}
private static class Edge {
int source;
int destination;
int weight;
Edge(int source, int destination, int weight) {
this.source = source;
this.destination = destination;
this.weight = weight;
}
}
private static class DisjointSet {
int[] parent;
int[] rank;
DisjointSet(int size) {
parent = new int[size];
rank = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
rank[i] = 0;
}
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void union(int x, int y) {
int root1 = find(x);
int root2 = find(y);
if (rank[root1] < rank[root2]) {
parent[root1] = root2;
} else if (rank[root1] > rank[root2]) {
parent[root2] = root1;
} else {
parent[root1] = root2;
rank[root2]++;
}
}
}
}
here's the rest of the Java code for implementing Kruskal's algorithm:
import java.util.*;
class KruskalAlgorithm {
public static void main(String[] args) {
int[][] graph = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
KruskalAlgorithm kruskal = new KruskalAlgorithm();
int[][] mst = kruskal.findMST(graph);
System.out.println("Minimum Spanning Tree:");
kruskal.printMST(mst);
}
public int[][] findMST(int[][] graph) {
int n = graph.length;
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (graph[i][j] != 0) {
edges.add(new Edge(i, j, graph[i][j]));
}
}
}
Collections.sort(edges);
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
int[][] mst = new int[n - 1][2];
int count = 0;
int index = 0;
while (count < n - 1) {
Edge e = edges.get(index++);
int p1 = find(parent, e.u);
int p2 = find(parent, e.v);
if (p1 != p2) {
mst[count][0] = e.u;
mst[count][1] = e.v;
count++;
parent[p1] = p2;
}
}
return mst;
}
private int find(int[] parent, int i) {
if (parent[i] == i) {
return i;
}
return find(parent, parent[i]);
}
private void printMST(int[][] mst) {
for (int[] edge : mst) {
System.out.println(edge[0] + " - " + edge[1]);
}
}
}
class Edge implements Comparable<Edge> {
int u;
int v;
int weight;
public Edge(int u, int v, int weight) {
this.u = u;
this.v = v;
this.weight = weight;
}
public int compareTo(Edge other) {
return this.weight - other.weight;
}
}
In this implementation, we first create a list of all edges in the graph, sorted by weight. We also create a parent array to keep track of the parent of each node in the union-find structure. We then iterate through the sorted list of edges, adding each edge to the minimum spanning tree if it does not create a cycle.
The find method uses path compression to find the parent of a node in the union-find structure. The printMST method simply prints out the edges in the minimum spanning tree.
To use this implementation, you can create a new instance of the KruskalAlgorithm class and call its findMST method with the graph represented as a 2D array of weights. The method returns the minimum spanning tree as a 2D array
Here is an implementation of Kruskal's Algorithm in Android:
public class Edge implements Comparable<Edge> {
int source, destination, weight;
@Override
public int compareTo(Edge edge) {
return this.weight - edge.weight;
}
}
public class KruskalAlgorithm {
int vertices;
Edge[] edges;
public KruskalAlgorithm(int vertices, Edge[] edges) {
this.vertices = vertices;
this.edges = edges;
}
public List<Edge> kruskalMST() {
List<Edge> result = new ArrayList<>();
// Sort edges by weight
Arrays.sort(edges);
// Initialize parent array for union-find algorithm
int[] parent = new int[vertices];
for (int i = 0; i < vertices; i++) {
parent[i] = i;
}
// Iterate over sorted edges and add them to the MST if they do not form a cycle
int index = 0;
while (result.size() < vertices - 1) {
Edge edge = edges[index++];
int sourceParent = findParent(parent, edge.source);
int destParent = findParent(parent, edge.destination);
if (sourceParent != destParent) {
result.add(edge);
parent[sourceParent] = destParent;
}
}
return result;
}
private int findParent(int[] parent, int vertex) {
if (parent[vertex] != vertex) {
parent[vertex] = findParent(parent, parent[vertex]);
}
return parent[vertex];
}
}
int vertices = 4;
Edge[] edges = new Edge[5];
edges[0] = new Edge(0, 1, 10);
edges[1] = new Edge(0, 2, 6);
edges[2] = new Edge(0, 3, 5);
edges[3] = new Edge(1, 3, 15);
edges[4] = new Edge(2, 3, 4);
KruskalAlgorithm kruskal = new KruskalAlgorithm(vertices, edges);
List<Edge> result = kruskal.kruskalMST();
here is the implementation of Kruskal's algorithm in C++:
#include <bits/stdc++.h>
using namespace std;
class Edge {
public:
int u, v, w;
Edge() {}
Edge(int u, int v, int w) {
this->u = u;
this->v = v;
this->w = w;
}
};
class DisjointSet {
public:
int *parent, *rank;
int n;
DisjointSet(int n) {
this->n = n;
parent = new int[n + 1];
rank = new int[n + 1];
for (int i = 0; i <= n; i++) {
rank[i] = 0;
parent[i] = i;
}
}
int find(int u) {
if (u != parent[u])
parent[u] = find(parent[u]);
return parent[u];
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (rank[x] > rank[y])
parent[y] = x;
else
parent[x] = y;
if (rank[x] == rank[y])
rank[y]++;
}
};
class Graph {
public:
int V, E;
Edge *edge;
Graph(int V, int E) {
this->V = V;
this->E = E;
edge = new Edge[E];
}
void addEdge(int u, int v, int w, int i) {
edge[i] = Edge(u, v, w);
}
void KruskalMST() {
sort(edge, edge + E, [](Edge &a, Edge &b) {
return a.w < b.w;
});
DisjointSet ds(V);
for (int i = 0; i < E; i++) {
int u = edge[i].u;
int v = edge[i].v;
int set_u = ds.find(u);
int set_v = ds.find(v);
if (set_u != set_v) {
cout << u << " - " << v << endl;
ds.merge(set_u, set_v);
}
}
}
};
int main() {
int V = 4, E = 5;
Graph g(V, E);
g.addEdge(0, 1, 10, 0);
g.addEdge(0, 2, 6, 1);
g.addEdge(0, 3, 5, 2);
g.addEdge(1, 3, 15, 3);
g.addEdge(2, 3, 4, 4);
g.KruskalMST();
return 0;
}
This code creates a Graph class that stores the number of vertices, number of edges, and an array of edges. The addEdge method adds an edge to the array of edges. The KruskalMST method sorts the edges in non-decreasing order of weight and iterates over each edge. It uses a DisjointSet class to keep track of the connected components and determines if adding the edge creates a cycle. If the edge does not create a cycle, it is added to the minimum spanning tree. Finally, the minimum spanning tree is printed to the console.
In the main function, a Graph object is created with four vertices and five edges. The edges are added to the graph using the addEdge method. The KruskalMST method is called to compute