如何使用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算法的示例代码：
立即学习“Java免费学习笔记（深入）”；
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实现图的最小生成树算法。
