Kruskal Algorithm Java

2025 年 5 月 6 日 | 阅读 3 分钟

Kruskal 算法是用于最小生成树的另一个最重要的算法。最小生成树是权重小于或等于所有生成树权重的生成树。

Java 中的 Kruskal 算法接受一个连通的无向图，并返回其最小生成树。给出的图表定义了 Kruskal 算法的工作原理。

以下是我们用于实现 Kruskal 算法的步骤：

从用户那里获取连通的无向图。
然后我们将所有边按权重从低到高排序。
选择权重最低的边并将其添加到生成树中。如果添加边会导致循环，则拒绝该边。
继续添加边，直到我们到达所有顶点。

让我们使用上述步骤在 Java 中实现 Kruskal 算法的代码。

KruskalExample.java

// import required classes and packages
import Java.util.*;

// create KruskalAlgorithm class to create minimum spanning tree of the given graph
class KruskalAlgorithm {
	//create class Edge to create an edge of the graph that implements Comparable interface 
	class Edge implements Comparable<Edge> {
		int source, destination, weight;

		public int compareTo(Edge edgeToCompare) {
			return this.weight - edgeToCompare.weight;
		}
	};

	// create class Subset for union
	class Subset {
		int parent, value;
	};
	
	//initialize vertices, edges and edgeArray
	int vertices, edges;
	Edge edgeArray[];

	// using constructor to create a graph
	KruskalAlgorithm(int vertices, int edges) {
		this.vertices = vertices;
		this.edges = edges;
		edgeArray = new Edge[this.edges];
		for (int i = 0; i < edges; ++i)
			edgeArray[i] = new Edge();	//create edge for all te edges given by the user
	}
	
	// create applyKruskal() method for applying Kruskal's Algorithm
	void applyKruskal() {
		
		// initialize finalResult array to store the final MST
		Edge finalResult[] = new Edge[vertices];
		int newEdge = 0;
		int index = 0;
		for (index = 0; index < vertices; ++index)
			finalResult[index] = new Edge();

		// using sort() method for sorting the edges
		Arrays.sort(edgeArray);
		
		// create an array of the vertices of type Subset for the subsets of vertices
		Subset subsetArray[] = new Subset[vertices];
		
		// aloocate memory to create vertices subsets
		for (index = 0; index < vertices; ++index)
			subsetArray[index] = new Subset();

		// it is used to create subset with single element
		for (int vertex = 0; vertex < vertices; ++vertex) {
			subsetArray[vertex].parent = vertex;
			subsetArray[vertex].value = 0;
		}
		index = 0;
		
		// use for loop to pick the smallers edge from the edges and increment the index for next iteration
		while (newEdge < vertices - 1) {
			// create an instance of Edge for next edge
			Edge nextEdge = new Edge();
			nextEdge = edgeArray[index++];
			
			int nextSource = findSetOfElement(subsetArray, nextEdge.source);
			int nextDestination = findSetOfElement(subsetArray, nextEdge.destination);
			
			//if the edge doesn't create cycle after including it, we add it in the result and increment the index
			if (nextSource != nextDestination) {
				finalResult[newEdge++] = nextEdge;
				performUnion(subsetArray, nextSource, nextDestination);
			}
		}
		for (index = 0; index < newEdge; ++index)
			System.out.println(finalResult[index].source + " - " + finalResult[index].destination + ": " + finalResult[index].weight);
	}
	
	// create findSetOfElement() method to get set of an element
	int findSetOfElement(Subset subsetArray[], int i) {
		if (subsetArray[i].parent != i)
			subsetArray[i].parent = findSetOfElement(subsetArray, subsetArray[i].parent);
		return subsetArray[i].parent;
	}
	
	// create performUnion() method to perform union of two sets
	void performUnion(Subset subsetArray[], int sourceRoot, int destinationRoot) {
		
		int nextSourceRoot = findSetOfElement(subsetArray, sourceRoot);
		int nextDestinationRoot = findSetOfElement(subsetArray, destinationRoot);

		if (subsetArray[nextSourceRoot].value < subsetArray[nextDestinationRoot].value)
			subsetArray[nextSourceRoot].parent = nextDestinationRoot;
		else if (subsetArray[nextSourceRoot].value > subsetArray[nextDestinationRoot].value)
			subsetArray[nextDestinationRoot].parent = nextSourceRoot;
		else {
			subsetArray[nextDestinationRoot].parent = nextSourceRoot;
			subsetArray[nextSourceRoot].value++;
		}
	}

	//main() method starts
	public static void main(String[] args) {
		
		int v, e;
		//create scanner class object to get input from user
		Scanner sc = new Scanner(System.in);
		
		//show custom message
		System.out.println("Enter number of vertices: ");
		
		//store user entered value into variable v
		v = sc.nextInt();
		
		//show custom message
		System.out.println("Enter number of edges");
		
		//store user entered value into variable e
		e = sc.nextInt();
		
		KruskalAlgorithm graph = new KruskalAlgorithm(v, e);		// use for creating Graph
		
		for(int i = 0; i < e; i++){
			System.out.println("Enter source value for edge["+ i +"]");
			graph.edgeArray[i].source = sc.nextInt();
			
			System.out.println("Enter destination value for edge["+ i +"]");
			graph.edgeArray[i].destination = sc.nextInt();
			
			System.out.println("Enter weight for edge["+i+"]");
			graph.edgeArray[i].weight = sc.nextInt();
		}
		
		// call applyKruskal() method to get MST
		graph.applyKruskal();
	}
}

输出