如何使用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中文網其他相關文章!