java 最小加权算法
时间: 2023-07-10 17:12:18 浏览: 41
Java中实现最小加权算法的常用方法是使用Prim算法或Kruskal算法。这两种算法都是经典的图论算法,用于求解带权无向图的最小生成树。其中,Prim算法是基于贪心策略的算法,从一个起点开始不断选择最小权值的边并加入到生成树中,直到所有顶点都被覆盖;Kruskal算法则是基于并查集的算法,将所有边按照权值排序,依次加入到生成树中,如果加入的边连接的两个顶点已经在同一个集合中,则跳过该边。
这里提供一个Prim算法的实现示例:
```java
public static int prim(int[][] graph) {
int n = graph.length;
boolean[] visited = new boolean[n];
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[0] = 0;
int res = 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;
res += dist[u];
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 res;
}
```
该算法的时间复杂度为O(n^2),其中n为图的顶点数。