如何使用java實作圖的最小生成樹演算法
概念介紹：
最小生成樹（Minimum Spanning Tree, MST）是指在一個帶權有向圖或無向圖中，找到一棵樹，使得其包含圖中的所有頂點且權值總和最小。最小生成樹演算法有多種，其中最經典的兩種演算法分別是Prim演算法和Kruskal演算法。
Prim演算法：
Prim演算法是一種基於點的貪婪演算法，它從一個頂點開始，然後逐漸擴展，直到產生整棵最小生成樹。以下是使用java實作Prim演算法的範例程式碼：
import java.util.Arrays;
public class PrimAlgorithm {
// 表示无穷大
private static final int INF = Integer.MAX_VALUE;
public static void primMST(int[][] graph) {
int vertices = graph.length;
// 创建一个数组用来保存最小生成树的顶点
int[] parent = new int[vertices];
// 创建一个数组用来保存每个顶点与最小生成树的最小权值
int[] key = new int[vertices];
// 创建一个数组用来标记顶点是否已经加入最小生成树
boolean[] mstSet = new boolean[vertices];
// 初始化key数组和mstSet数组的值
Arrays.fill(key, INF);
Arrays.fill(mstSet, false);
//将第一个顶点加入最小生成树
key[0] = 0;
parent[0] = -1;
for (int count = 0; count < vertices - 1; count++) {
// 选择key值最小的顶点
int minKey = getMinKey(key, mstSet);
mstSet[minKey] = true;
// 更新与该顶点相邻的顶点的key值
for (int v = 0; v < vertices; v++) {
if (graph[minKey][v] != 0 && !mstSet[v] && graph[minKey][v] < key[v]) {
parent[v] = minKey;
key[v] = graph[minKey][v];
}
}
}
// 输出最小生成树
printMST(parent, graph);
}
// 获得key值最小的顶点
private static int getMinKey(int[] key, boolean[] mstSet) {
int minKey = INF, minIndex = -1;
for (int v = 0; v < key.length; v++) {
if (!mstSet[v] && key[v] < minKey) {
minKey = key[v];
minIndex = v;
}
}
return minIndex;
}
// 输出最小生成树
private static void printMST(int[] parent, int[][] graph) {
System.out.println("Edge Weight");
for (int i = 1; i < graph.length; i++) {
System.out.println(parent[i] + " - " + i + " " + graph[i][parent[i]]);
}
}
public static void main(String[] args) {
int[][] graph = {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0}};
primMST(graph);
}
}登入後複製
Kruskal演算法：
Kruskal演算法是一種基於邊的貪婪演算法，它依照權值從小到大的順序選擇邊，並且只選擇不會產生環的邊，直到生成整棵最小生成樹。以下是使用java實作Kruskal演算法的範例程式碼：
import java.util.*;
class Edge implements Comparable<Edge> {
int src, dest, weight;
public int compareTo(Edge compareEdge) {
return this.weight - compareEdge.weight;
}
}
class KruskalAlgorithm {
public List<Edge> kruskalMST(List<Edge> edges, int vertices) {
List<Edge> result = new ArrayList<>();
Collections.sort(edges);
int[] parent = new int[vertices];
for (int i = 0; i < vertices; i++) {
parent[i] = i;
}
int count = 0, i = 0;
while (count < vertices - 1) {
Edge currentEdge = edges.get(i);
int x = find(parent, currentEdge.src);
int y = find(parent, currentEdge.dest);
if (x != y) {
result.add(currentEdge);
union(parent, x, y);
count++;
}
i++;
}
return result;
}
private int find(int[] parent, int vertex) {
if (parent[vertex] != vertex) {
parent[vertex] = find(parent, parent[vertex]);
}
return parent[vertex];
}
private void union(int[] parent, int x, int y) {
int xSet = find(parent, x);
int ySet = find(parent, y);
parent[xSet] = ySet;
}
public static void main(String[] args) {
int vertices = 4;
List<Edge> edges = new ArrayList<>();
edges.add(new Edge(0, 1, 10));
edges.add(new Edge(0, 2, 6));
edges.add(new Edge(0, 3, 5));
edges.add(new Edge(1, 3, 15));
edges.add(new Edge(2, 3, 4));
KruskalAlgorithm kruskal = new KruskalAlgorithm();
List<Edge> result = kruskal.kruskalMST(edges, vertices);
System.out.println("Edge Weight");
for (Edge edge : result) {
System.out.println(edge.src + " - " + edge.dest + " " + edge.weight);
}
}
}登入後複製
以上是使用java實作Prim演算法和Kruskal演算法的範例程式碼，它們都是實作圖的最小生成樹演算法的經典方法。透過學習和理解這些程式碼，可以更好地理解和掌握如何使用java實現圖的最小生成樹演算法。
以上是如何使用java實作圖的最小生成樹演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！
