21xrx.com
2024-11-22 06:52:46 Friday
登录
文章检索 我的文章 写文章
Java实现最小生成树算法
2023-06-12 05:32:38 深夜i     --     --
最小生成树 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]);

    }

  }

}

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复