prime算法java实现
时间: 2023-11-29 15:04:52 浏览: 42
以下是Java实现Prime算法的示例代码:
```java
import java.util.*;
public class PrimeAlgorithm {
private static final int INF = Integer.MAX_VALUE; // 定义正无穷
public static void main(String[] args) {
int[][] graph = { // 定义图的邻接矩阵
{0, 2, 4, 0, 0, 0},
{2, 0, 2, 4, 2, 0},
{4, 2, 0, 0, 3, 0},
{0, 4, 0, 0, 3, 2},
{0, 2, 3, 3, 0, 2},
{0, 0, 0, 2, 2, 0}
};
int[] dist = prime(graph, 0); // 从0号节点开始构造最小生成树
System.out.println(Arrays.toString(dist)); // 输出最小生成树的各个节点到起点的距离
}
public static int[] prime(int[][] graph, int start) {
int n = graph.length;
int[] dist = new int[n]; // 存储最小生成树的各个节点到起点的距离
boolean[] visited = new boolean[n]; // 存储节点是否已经被访问
Arrays.fill(dist, INF); // 初始化距离为正无穷
dist[start] = 0; // 起点到自身的距离为0
for (int i = 0; i < n; i++) {
int u = -1;
for (int j = 0; j < n; j++) { // 找到未访问节点中距离起点最近的节点
if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
u = j;
}
}
visited[u] = true; // 标记该节点已经被访问
for (int v = 0; v < n; v++) { // 更新与该节点相邻的节点的距离
if (!visited[v] && graph[u][v] != 0 && graph[u][v] < dist[v]) {
dist[v] = graph[u][v];
}
}
}
return dist;
}
}
```