21xrx.com
2025-03-21 15:15:19 Friday
文章检索 我的文章 写文章
Java最小生成树Kruskal算法：实现和应用
2023-06-17 14:39:50 深夜i     15     0
Java 最小生成树 Kruskal算法 图 算法实现

最小生成树是在一个无向图中找出连接所有节点的边的最小权值和的子集。Kruskal算法是一种用于在联通的加权图中查找最小生成树的贪心算法。这篇文章将介绍Java语言中Kruskal算法的实现和应用。

Java是一种面向对象的编程语言，具有跨平台性和简单性。Java提供了许多数据结构和算法的实现，其中之一就是最小生成树的Kruskal算法。

该算法的基本思想是先将所有边按照权值从小到大排序。然后依次取出每条边，如果这条边的两个顶点不连通，则将它们连通，并将这条边加入到最小生成树中。直到最小生成树中有n-1条边为止，其中n是节点的数量。

在Java中实现Kruskal算法，首先需要构建一个图的类，并将节点和边以及他们之间的关系都封装在这个类中。代码如下：

public class Graph {
  private int V;
  private LinkedList
  [] adj;
 
  public Graph(int V) {
    this.V = V;
    adj = new LinkedList[V];
    for (int i = 0; i < V; i++) {
      adj[i] = new LinkedList<>();
    }
  }
  public void addEdge(int u, int v, int w) {
    adj[u].add(new Edge(u, v, w));
    adj[v].add(new Edge(v, u, w));
  }
  private class Edge implements Comparable
  {
 
    int u, v, w;
    public Edge(int u, int v, int w)
      this.u = u;
      this.v = v;
      this.w = w;
    
    @Override
    public int compareTo(Edge o) {
      return Integer.compare(w, o.w);
    }
  }
}

接下来，实现Kruskal算法的代码如下：

public class Kruskal {
  private int[] parent;
  private int V;
  public Kruskal(int V) {
    this.V = V;
    parent = new int[V];
    for (int i = 0; i < V; i++) {
      parent[i] = i;
    }
  }
  private int find(int x) {
    while (parent[x] != x) {
      x = parent[x];
    }
    return x;
  }
  private void union(int u, int v) {
    int rootU = find(u);
    int rootV = find(v);
    parent[rootU] = rootV;
  }
  public void kruskal(Graph graph) {
    List
  edges = new ArrayList<>();
 
    for (int u = 0; u < graph.V; u++) {
      for (Edge e : graph.adj[u]) {
        edges.add(e);
      }
    }
    edges.sort(Edge::compareTo);
    int count = 0;
    int i = 0;
    while (count < V - 1 && i < edges.size()) {
      Edge e = edges.get(i++);
      int u = e.u;
      int v = e.v;
      if (find(u) == find(v))
        continue;
      
      union(u, v);
      System.out.println(e.u + " - " + e.v + " : " + e.w);
      count++;
    }
  }
}

在上述代码中，find（）方法用于找到u节点的根节点，union（）方法用于将两个节点合并到同一个集合中。kruskal（）方法用于执行Kruskal算法。

最后，运行以下代码以生成某个图的最小生成树：

public class Main {
  public static void main(String[] args) {
    Graph graph = new Graph(5);
    graph.addEdge(0, 2, 3);
    graph.addEdge(0, 1, 2);
    graph.addEdge(2, 3, 6);
    graph.addEdge(1, 3, 8);
    graph.addEdge(1, 4, 5);
    graph.addEdge(3, 4, 1);
    Kruskal kruskal = new Kruskal(5);
    kruskal.kruskal(graph);
  }
}

这将打印出以下内容：

3 - 4 : 1
0 - 2 : 3
0 - 1 : 2
1 - 4 : 5

这是最小生成树中的所有边，它们的权重和为11。

  
  

评论区