Skip to content

Commit 43e6ee6

Browse files
author
Lord-of-Algorithms
committed
Add Kruskal's algorithm for MST construction
1 parent da9b586 commit 43e6ee6

File tree

3 files changed

+187
-0
lines changed

3 files changed

+187
-0
lines changed

‎src/graph/Edge.java

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package graph;
2+
3+
import java.util.Objects;
4+
5+
/**
6+
* Represents an edge in a graph, defined by a source vertex,
7+
* a destination vertex, and a weight.
8+
*/
9+
public class Edge {
10+
private final Vertex source;
11+
private final Vertex destination;
12+
private final int weight;
13+
14+
public Edge(Vertex source, Vertex destination, int weight) {
15+
this.source = source;
16+
this.destination = destination;
17+
this.weight = weight;
18+
}
19+
20+
public Vertex getSource() {
21+
return source;
22+
}
23+
24+
public Vertex getDestination() {
25+
return destination;
26+
}
27+
28+
public int getWeight() {
29+
return weight;
30+
}
31+
32+
@Override
33+
public boolean equals(Object o) {
34+
if (this == o) return true;
35+
if (o == null || getClass() != o.getClass()) return false;
36+
Edge edge = (Edge) o;
37+
return weight == edge.weight &&
38+
Objects.equals(source, edge.source) &&
39+
Objects.equals(destination, edge.destination);
40+
}
41+
42+
@Override
43+
public int hashCode() {
44+
return Objects.hash(source, destination, weight);
45+
}
46+
47+
@Override
48+
public String toString() {
49+
return source + "" + destination + "(" + weight + ")";
50+
}
51+
}

‎src/graph/mst/kruskal/KruskalMstMain.java

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
package graph.mst.kruskal;
2+
3+
import graph.Edge;
4+
import graph.Vertex;
5+
import graph.VertexImpl;
6+
7+
import java.util.ArrayList;
8+
import java.util.Comparator;
9+
import java.util.List;
10+
11+
/**
12+
* Demonstrates the use of Kruskal's algorithm to find the minimum spanning tree (MST) of a graph.
13+
* This class highlights how Kruskal's algorithm is particularly suited for graphs represented as a list of edges,
14+
* as it processes edges by increasing weight, irrespective of their position in the graph. This edge list representation
15+
* is used because Kruskal's algorithm does not require direct access to the graph's adjacency structure, making it
16+
* efficient and straightforward for calculating the MST in graphs where edge connectivity is the primary concern.
17+
* <p>
18+
* The main method sets up vertices and edges, then uses Kruskal's algorithm to calculate and display the MST.
19+
*/
20+
public class KruskalMstMain {
21+
public static void main(String[] args) {
22+
23+
List<Vertex> vertices = new ArrayList<>();
24+
// Create vertices
25+
Vertex a = new VertexImpl("A");
26+
Vertex b = new VertexImpl("B");
27+
Vertex c = new VertexImpl("C");
28+
Vertex d = new VertexImpl("D");
29+
30+
vertices.add(a);
31+
vertices.add(b);
32+
vertices.add(c);
33+
vertices.add(d);
34+
35+
List<Edge> edges = new ArrayList<>();
36+
// Set edges between vertices with specified weights
37+
edges.add(new Edge(a, b, 1));
38+
edges.add(new Edge(d, b, 2));
39+
edges.add(new Edge(b, c, 3));
40+
edges.add(new Edge(a, d, 4));
41+
edges.add(new Edge(d, c, 5));
42+
43+
// Calculate the MST using Kruskal's algorithm
44+
List<Edge> mst = buildMst(vertices, edges);
45+
System.out.println("MST: " + mst);
46+
}
47+
48+
/**
49+
* Constructs the minimum spanning tree (MST) for a graph represented by vertices and edges.
50+
* Assumes that the graph is connected.
51+
*/
52+
private static List<Edge> buildMst(List<Vertex> vertices, List<Edge> edges) {
53+
if (vertices == null || vertices.isEmpty()) {
54+
throw new IllegalArgumentException("Vertex list cannot be null or empty.");
55+
}
56+
if (edges == null || edges.isEmpty()) {
57+
throw new IllegalArgumentException("Edge list cannot be null or empty.");
58+
}
59+
60+
List<Edge> mst = new ArrayList<>();
61+
62+
// Sorting edges by weight
63+
edges.sort(new Comparator<Edge>() {
64+
@Override
65+
public int compare(Edge edge1, Edge edge2) {
66+
return edge1.getWeight() - edge2.getWeight();
67+
}
68+
});
69+
UnionFind uf = new UnionFind(vertices);
70+
71+
for (Edge edge : edges) {
72+
if (uf.find(edge.getSource()) != uf.find(edge.getDestination())) {
73+
mst.add(edge);
74+
uf.union(edge.getSource(), edge.getDestination());
75+
}
76+
}
77+
return mst;
78+
}
79+
}

‎src/graph/mst/kruskal/UnionFind.java

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package graph.mst.kruskal;
2+
3+
import graph.Vertex;
4+
5+
import java.util.HashMap;
6+
import java.util.List;
7+
import java.util.Map;
8+
9+
/**
10+
* Implements the union-find data structure.
11+
*/
12+
class UnionFind {
13+
private final Map<Vertex, Vertex> parent;
14+
private final Map<Vertex, Integer> rank;
15+
16+
/**
17+
* Constructs a union-find structure with a list of initial vertices.
18+
* Each vertex is initially its own set with a rank of 0.
19+
*/
20+
UnionFind(List<Vertex> vertices) {
21+
parent = new HashMap<>();
22+
rank = new HashMap<>();
23+
for (Vertex vertex : vertices) {
24+
parent.put(vertex, vertex);
25+
rank.put(vertex, 0);
26+
}
27+
}
28+
29+
/**
30+
* Finds the representative of the set containing the specified vertex.
31+
* Implements path compression.
32+
*/
33+
Vertex find(Vertex vertex) {
34+
if (!vertex.equals(parent.get(vertex))) {
35+
parent.put(vertex, find(parent.get(vertex)));
36+
}
37+
return parent.get(vertex);
38+
}
39+
40+
/**
41+
* Unites the two sets that contain vertex 'x' and 'y'.
42+
*/
43+
void union(Vertex x, Vertex y) {
44+
Vertex rootX = find(x);
45+
Vertex rootY = find(y);
46+
if (!rootX.equals(rootY)) {
47+
if (rank.get(rootX) < rank.get(rootY)) {
48+
parent.put(rootX, rootY);
49+
} else if (rank.get(rootX) > rank.get(rootY)) {
50+
parent.put(rootY, rootX);
51+
} else {
52+
parent.put(rootY, rootX);
53+
rank.put(rootX, rank.get(rootX) + 1);
54+
}
55+
}
56+
}
57+
}

0 commit comments

Comments
 (0)