21xrx.com
2025-06-29 08:32:02 Sunday
文章检索 我的文章 写文章
Java实现最小生成树的方法——Prim算法和Kruskal算法
2023-06-17 04:41:03 深夜i     26     0
最小生成树 Prim算法 Kruskal算法

在图论中，最小生成树是指一个连通图的生成树中边的权值和最小的生成树。最小生成树在实际问题中有广泛的应用，例如通信网络、电路设计、自然语言处理等。这篇文章将介绍Java中实现最小生成树的两种方法——Prim算法和Kruskal算法，并提供相应的代码案例。

1. Prim算法

Prim算法是一种贪心算法，基本思想是从一个顶点开始，每次将与当前已经连通顶点集合相连且权值最小的边加入到连通顶点集合中，直到所有顶点都被加入到连通集合中为止。Prim算法的时间复杂度为O（V²），其中V代表顶点数。

下面是Java中Prim算法的示例代码：

public static int prim(int[][] graph) {
  int n = graph.length;
  int[] dist = new int[n]; // 存储最小生成树到每个点的最短距离
  boolean[] visited = new boolean[n]; // 标记每个点是否已经被访问
  Arrays.fill(dist, Integer.MAX_VALUE);
  dist[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];
      }
    }
  }
  int sum = 0;
  for (int i = 0; i < n; i++) {
    sum += dist[i];
  }
  return sum;
}

2. Kruskal算法

Kruskal算法也是一种贪心算法，基本思想是将所有边按照权值从小到大排序，依次将每条边加入到最小生成树中，直到加入n-1条边为止。Kruskal算法的时间复杂度为O(ElogE)，其中E代表边数。

下面是Java中Kruskal算法的示例代码：

public static int kruskal(int[][] graph) {
  int n = graph.length;
  List
  edges = new ArrayList<>();
 
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (graph[i][j] != 0) {
        edges.add(new int[]{graph[i][j], i, j});
      }
    }
  }
  edges.sort(Comparator.comparingInt(a -> a[0])); // 按照边的权值从小到大排序
  int[] parent = new int[n];
  for (int i = 0; i < n; i++) {
    parent[i] = i;
  }
  int sum = 0;
  for (int[] edge : edges) {
    int weight = edge[0], u = edge[1], v = edge[2];
    if (find(parent, u) != find(parent, v)) {
      union(parent, u, v);
      sum += weight;
    }
    if (count(parent) == 1)
      break;
    
  }
  return sum;
}
private static int find(int[] parent, int x) {
  if (parent[x] == x)
    return x;
  
  return parent[x] = find(parent, parent[x]);
}
private static void union(int[] parent, int x, int y) {
  int px = find(parent, x);
  int py = find(parent, y);
  if (px != py) {
    parent[px] = py;
  }
}
private static int count(int[] parent) {
  int n = parent.length;
  int count = 0;
  for (int i = 0; i < n; i++) {
    if (parent[i] == i) {
      count++;
    }
  }
  return count;
}

以上就是Java中实现最小生成树的两种方法，分别是Prim算法和Kruskal算法。通过对两种方法的介绍以及代码案例的演示，可以更好地理解最小生成树的概念和实现方法。

  
  

评论区