Java를 사용하여 Kruskal 알고리즘을 구현하는 방법

import java.util.*; class Edge implements Comparable { int src, dest, weight; public int compareTo(Edge edge) { return this.weight - edge.weight; } } class Subset { int parent, rank; } class Graph { int V, E; Edge[] edges; public 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(Subset[] subsets, int i) { if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent; } void union(Subset[] subsets, int x, int y) { int xroot = find(subsets, x); int yroot = find(subsets, y); if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; else { subsets[yroot].parent = xroot; subsets[xroot].rank++; } } 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); Subset[] subsets = new Subset[V]; for (i = 0; i < V; ++i) subsets[i] = new Subset(); for (int v = 0; v < V; ++v) { subsets[v].parent = v; subsets[v].rank = 0; } i = 0; while (e < V - 1) { Edge next_edge = edges[i++]; int x = find(subsets, next_edge.src); int y = find(subsets, next_edge.dest); if (x != y) { result[e++] = next_edge; union(subsets, x, y); } } System.out.println("Following are the edges in the constructed MST:"); int minimumCost = 0; for (i = 0; i < e; ++i) { System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight); minimumCost += result[i].weight; } System.out.println("Minimum Cost Spanning Tree: " + minimumCost); } } 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(); } }

Following are the edges in the constructed MST: 2 -- 3 == 4 0 -- 3 == 5 0 -- 1 == 10 Minimum Cost Spanning Tree: 19