如何使用Java實現最小生成樹演算法
最小生成樹演算法是圖論中的一個經典問題，用於求解一個帶權重的連通圖的最小生成樹。本文將介紹如何使用Java語言來實作這個演算法，並提供具體的程式碼範例。
以下是Prim演算法的Java實作範例：
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
class Edge implements Comparable<Edge> {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
public class Prim {
public static List<Edge> calculateMST(List<List<Edge>> graph) {
int n = graph.size();
boolean[] visited = new boolean[n];
Queue<Edge> pq = new PriorityQueue<>();
// Start from vertex 0
int start = 0;
visited[start] = true;
for (Edge e : graph.get(start)) {
pq.offer(e);
}
List<Edge> mst = new ArrayList<>();
while (!pq.isEmpty()) {
Edge e = pq.poll();
int from = e.from;
int to = e.to;
int weight = e.weight;
if (visited[to]) {
continue;
}
visited[to] = true;
mst.add(e);
for (Edge next : graph.get(to)) {
if (!visited[next.to]) {
pq.offer(next);
}
}
}
return mst;
}
}以下是Kruskal演算法的Java實作範例：
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
class Edge implements Comparable<Edge> {
int from;
int to;
int weight;
public Edge(int from, int to, int weight) {
this.from = from;
this.to = to;
this.weight = weight;
}
@Override
public int compareTo(Edge other) {
return Integer.compare(this.weight, other.weight);
}
}
public class Kruskal {
public static List<Edge> calculateMST(List<Edge> edges, int n) {
List<Edge> mst = new ArrayList<>();
Collections.sort(edges);
int[] parent = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
for (Edge e : edges) {
int from = e.from;
int to = e.to;
int weight = e.weight;
int parentFrom = findParent(from, parent);
int parentTo = findParent(to, parent);
if (parentFrom != parentTo) {
mst.add(e);
parent[parentFrom] = parentTo;
}
}
return mst;
}
private static int findParent(int x, int[] parent) {
if (x != parent[x]) {
parent[x] = findParent(parent[x], parent);
}
return parent[x];
}
}import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<List<Edge>> graph = new ArrayList<>();
graph.add(new ArrayList<>());
graph.add(new ArrayList<>());
graph.add(new ArrayList<>());
graph.add(new ArrayList<>());
graph.get(0).add(new Edge(0, 1, 2));
graph.get(0).add(new Edge(0, 2, 3));
graph.get(1).add(new Edge(1, 0, 2));
graph.get(1).add(new Edge(1, 2, 1));
graph.get(1).add(new Edge(1, 3, 5));
graph.get(2).add(new Edge(2, 0, 3));
graph.get(2).add(new Edge(2, 1, 1));
graph.get(2).add(new Edge(2, 3, 4));
graph.get(3).add(new Edge(3, 1, 5));
graph.get(3).add(new Edge(3, 2, 4));
List<Edge> mst = Prim.calculateMST(graph);
System.out.println("Prim算法得到的最小生成树：");
for (Edge e : mst) {
System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
}
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 2));
edges.add(new Edge(0, 2, 3));
edges.add(new Edge(1, 2, 1));
edges.add(new Edge(1, 3, 5));
edges.add(new Edge(2, 3, 4));
mst = Kruskal.calculateMST(edges, 4);
System.out.println("Kruskal算法得到的最小生成树：");
for (Edge e : mst) {
System.out.println(e.from + " -> " + e.to + "，权重：" + e.weight);
}
}
}透過執行上面的範例程序，可以得到以下輸出結果：
Prim算法得到的最小生成树： 0 -> 1，权重：2 1 -> 2，权重：1 2 -> 3，权重：4 Kruskal算法得到的最小生成树： 1 -> 2，权重：1 0 -> 1，权重：2 2 -> 3，权重：4
以上就是使用Java實作最小生成樹演算法的具體程式碼範例。透過這些範例程式碼，讀者可以更好地理解和學習最小生成樹演算法的實現過程和原理。希望本文對讀者有幫助。
以上是如何使用java實作最小生成樹演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
