How to implement Prim's algorithm using java

How to use Java to implement Prim's algorithm

The Prim algorithm is a classic algorithm for solving minimum spanning trees and can be used to solve various network optimization problems. In this article, we will introduce how to implement Prim's algorithm using Java language and provide corresponding code examples.

1. Algorithm idea
   The basic idea of ​​Prim algorithm is to start from an initial vertex and gradually expand to generate a minimum spanning tree. The specific steps are as follows:

1) Initialize the minimum spanning tree to be empty, select an initial vertex v to join the minimum spanning tree set.
2) Perform the following steps in a loop until the minimum spanning tree set contains all vertices:
a) Select a vertex u from outside the minimum spanning tree set such that the weight of u to the vertex in the minimum spanning tree set is the smallest.
b) Add vertex u to the minimum spanning tree set and record the weights of edges (u, v).
c) Update the weight of u to the vertex outside the minimum spanning tree set. If the weight of a vertex is smaller, update the weight of the vertex to the vertex in the minimum spanning tree set.

2. Java code implementation
   The following is a code example to implement Prim's algorithm using Java language:

import java.util.Arrays;

public class PrimAlgorithm {
    // 假设使用邻接矩阵表示图
    public int prim(int[][] graph) {
        int numVertex = graph.length; // 图中顶点的个数
        int[] lowCost = new int[numVertex]; // 存储顶点到最小生成树集合的最小权值
        boolean[] visited = new boolean[numVertex]; // 标记顶点是否已经加入最小生成树集合
        int[] parent = new int[numVertex]; // 存储顶点的父节点
        Arrays.fill(lowCost, Integer.MAX_VALUE); // 初始化最小权值为无穷大
        Arrays.fill(visited, false); // 初始化顶点未访问

        // 从顶点0开始构建最小生成树
        lowCost[0] = 0; // 顶点0到最小生成树集合的最小权值为0
        parent[0] = -1; // 顶点0没有父节点

        // 循环直到最小生成树集合包含所有顶点
        for (int i = 0; i < numVertex - 1; i++) {
            // 选择一个顶点u使得u到最小生成树集合中的顶点的权值最小
            int u = -1;
            for (int j = 0; j < numVertex; j++) {
                if (!visited[j] && (u == -1 || lowCost[j] < lowCost[u])) {
                    u = j;
                }
            }

            visited[u] = true; // 将顶点u加入最小生成树集合

            // 更新u到最小生成树集合外的顶点的权值
            for (int v = 0; v < numVertex; v++) {
                if (!visited[v] && graph[u][v] != 0 && graph[u][v] < lowCost[v]) {
                    lowCost[v] = graph[u][v];
                    parent[v] = u;
                }
            }
        }

        int totalPrice = 0;
        for (int i = 1; i < numVertex; i++) {
            totalPrice += graph[parent[i]][i];
        }

        return totalPrice;
    }

    public static void main(String[] args) {
        int[][] graph = { {0, 2, 0, 6, 0},
                          {2, 0, 3, 8, 5},
                          {0, 3, 0, 0, 7},
                          {6, 8, 0, 0, 9},
                          {0, 5, 7, 9, 0} };

        PrimAlgorithm primAlgorithm = new PrimAlgorithm();
        int totalPrice = primAlgorithm.prim(graph);
        System.out.println("Total weight of minimum spanning tree: " + totalPrice);
    }
}

In the above code, we use the adjacency matrix to represent the graph, and use Dijkstra's algorithm finds the total weight of the minimum spanning tree. In the example, we use a 5-vertex graph to demonstrate the use of the algorithm.

3. Summary
   Through the introduction of this article, we understand the basic idea of ​​Prim's algorithm and how to implement the algorithm using Java language. I hope this article can help readers better understand Prim's algorithm and be able to use it flexibly in practical applications.

The above is the detailed content of How to implement Prim's algorithm using java. For more information, please follow other related articles on the PHP Chinese website!