21xrx.com
2025-03-21 13:25:57 Friday
文章检索 我的文章 写文章
Java实现最小生成树算法
2023-06-12 05:32:38 深夜i     7     0
最小生成树 Kruskal算法 Prim算法 Java实现

最小生成树是图论中的一个概念，它是指在一个带权连通图中，所有边的权值之和最小的生成树。在实际中，最小生成树算法可以被用来解决许多问题，比如网络连接、电路设计和道路建设等。本文将介绍如何用Java实现最小生成树算法。

在Java中，最小生成树算法可以使用Kruskal算法或Prim算法实现。其中，Kruskal算法通过不断加边的方式生成最小生成树。它的实现过程包括以下步骤：

1. 将所有的边按照权值从小到大排序。

2. 依次加入边，如果新加的边不会形成环，则将它加入最小生成树中。

3. 直到最小生成树中有n-1条边为止(n为点的个数)。

代码示例如下：

public class Kruskal {
  public void kruskal(int[][] graph) {
    int[] parent = new int[graph.length];
    int min, u = 0, v = 0, noOfEdges = 1, total = 0;
    for (int i = 0; i < graph.length; i++) {
      parent[i] = 0;
    }
    while (noOfEdges < graph.length) {
      min = 999;
      for (int i = 0; i < graph.length; i++) {
        for (int j = 0; j < graph.length; j++) {
          if (graph[i][j] < min) {
            min = graph[i][j];
            u = i;
            v = j;
          }
        }
      }
      while (parent[u] != 0) {
        u = parent[u];
      }
      while (parent[v] != 0) {
        v = parent[v];
      }
      if (u != v) {
        System.out.printf("\n Edge %d:(%d %d) distance:%d", noOfEdges++, u, v, min);
        total += min;
        parent[v] = u;
      }
      graph[u][v] = graph[v][u] = 999;
    }
    System.out.printf("\n Minimun cost=%d", total);
  }
}

另外，Prim算法是一种贪心算法，它从一个点开始，不断加入最小的边，直到生成完整的最小生成树。它的实现过程包括以下步骤：

1. 初始化一个集合X，包括任意一个节点。

2. 从集合X中找到与之相邻的边中最小的那条，并将它的另一个节点加入集合X中。

3. 重复步骤2，直到X包含所有节点。

代码示例如下：

public class Prim {
  public void prim(int[][] graph, int start) {
    int[] dist = new int[graph.length];
    boolean[] visited = new boolean[graph.length];
    visited[start] = true;
    for (int i = 0; i < graph.length; i++) {
      dist[i] = graph[start][i];
    }
    for (int i = 0; i < graph.length - 1; i++) {
      int min = 999;
      int u = -1;
      for (int j = 0; j < graph.length; j++) {
        if (!visited[j] && dist[j] < min) {
          min = dist[j];
          u = j;
        }
      }
      visited[u] = true;
      for (int v = 0; v < graph.length; v++) {
        if (!visited[v] && graph[u][v] < dist[v]) {
          dist[v] = graph[u][v];
        }
      }
      System.out.printf("\n Edge %d:(%d %d) distance:%d", i, u, parent[u], dist[u]);
    }
  }
}
  
  

评论区