《Java实现最小生成树算法》 |21xrx.com

《Java实现最小生成树算法》

2023-06-14 22:30:48 深夜i -- --

最小生成树 Java 邻接表

最小生成树是图论中常用的一种算法，用于在一个有权的连通图中找到一棵边权值之和最小的生成树。本文将介绍如何用Java语言实现最小生成树算法，并给出代码案例。

首先，我们需要定义一个图的数据结构，可以使用邻接表或邻接矩阵来表示。这里我们使用邻接表来实现。


class Edge implements Comparable
  {
 
  int to, w;
  public Edge(int to, int w) this.to = to; this.w = w;
  public int compareTo(Edge other) return this.w - other.w;
}
class Graph {
  int V;
  List
  [] adj;
 
  public Graph(int V) {
    this.V = V;
    adj = new ArrayList[V];
    for (int i = 0; i < V; i++)
      adj[i] = new ArrayList<>();
  }
  public void addEdge(int u, int v, int w) {
    adj[u].add(new Edge(v, w));
    adj[v].add(new Edge(u, w));
  }
}

上述代码中，Edge表示一条边，其中to表示边的终点，w表示边的权值。Graph则表示一个图，其中V表示顶点数，adj则是一个邻接表数组，存储每个顶点所连的边。

接下来，我们用Prim算法来实现最小生成树的查找，Prim算法的核心是用一个优先队列来存储当前已经在树中的顶点到非树顶点的最小边，并使用一个标记数组来标记每个顶点是否在树中。


public List
  primMST(Graph G) {
 
  boolean[] visited = new boolean[G.V];
  int[] parent = new int[G.V];
  Arrays.fill(parent, -1);
  PriorityQueue
  pq = new PriorityQueue<>();
 
  pq.add(new Edge(0, 0));
  List
  res = new ArrayList<>();
 
  while (!pq.isEmpty()) {
    Edge cur = pq.poll();
    if (visited[cur.to]) continue;
    visited[cur.to] = true;
    if (cur.w > 0) res.add(cur);
    for (Edge e : G.adj[cur.to]) {
      if (!visited[e.to])
        pq.add(new Edge(e.to, e.w));
    }
  }
  return res;
}

上述代码中，visited数组用于标记每个顶点是否在树中，parent数组用于存储每个顶点在树中的父节点。pq表示一个优先队列，按边权值从小到大排序，存储当前已经在树中的顶点到非树顶点的最小边。res用于存储最小生成树的边。

至此，我们已经完成了最小生成树算法的Java实现。下面是一个完整的代码案例，用于演示最小生成树算法的功能。


import java.util.*;
class Edge implements Comparable
  {
 
  int to, w;
  public Edge(int to, int w) this.to = to; this.w = w;
  public int compareTo(Edge other) return this.w - other.w;
}
class Graph {
  int V;
  List
  [] adj;
 
  public Graph(int V) {
    this.V = V;
    adj = new ArrayList[V];
    for (int i = 0; i < V; i++)
      adj[i] = new ArrayList<>();
  }
  public void addEdge(int u, int v, int w) {
    adj[u].add(new Edge(v, w));
    adj[v].add(new Edge(u, w));
  }
}
public class Main {
  public static void main(String[] args) {
    Graph G = new Graph(5);
    G.addEdge(0, 1, 2);
    G.addEdge(0, 2, 3);
    G.addEdge(1, 2, 4);
    G.addEdge(2, 3, 5);
    G.addEdge(3, 4, 1);
    List
  res = primMST(G);
 
    int sum = 0;
    for (Edge e : res) {
      System.out.printf("(%d -> %d) %d\n", e.to, parent[e.to], e.w);
      sum += e.w;
    }
    System.out.println("MST weight = " + sum);
  }
  public static List
  primMST(Graph G) {
 
    boolean[] visited = new boolean[G.V];
    int[] parent = new int[G.V];
    Arrays.fill(parent, -1);
    PriorityQueue
  pq = new PriorityQueue<>();
 
    pq.add(new Edge(0, 0));
    List
  res = new ArrayList<>();
 
    while (!pq.isEmpty()) {
      Edge cur = pq.poll();
      if (visited[cur.to]) continue;
      visited[cur.to] = true;
      if (cur.w > 0) res.add(cur);
      for (Edge e : G.adj[cur.to]) {
        if (!visited[e.to])
          pq.add(new Edge(e.to, e.w));
      }
    }
    return res;
  }
}

上一篇: idea打包java可执行jar包

下一篇: Java的发展史及影响因素

评论区

()

相似文章