java实现prim算法

Prim算法是一种用于求解最小生成树的算法，它的实现方式比较简单。下面是Java实现Prim算法的示例代码：

import java.util.Arrays;

public class PrimAlgorithm {
    // 顶点个数
    private int vertexCount;
    // 无穷大表示两个顶点不连通
    private static final int INF = Integer.MAX_VALUE;
    // 存储顶点数据的数组
    private char[] vertexData;
    // 存储边的权值的矩阵
    private int[][] weightMatrix;

    public PrimAlgorithm(char[] vertexData, int[][] weightMatrix) {
        this.vertexCount = vertexData.length;
        this.vertexData = vertexData;
        this.weightMatrix = weightMatrix;
    }

    /**
     * 执行Prim算法，获取最小生成树
     */
    public void prim() {
        // 存储从已经访问过的顶点到未访问过的顶点的最短距离
        int[] minDistances = new int[vertexCount];
        // 存储已经访问过的顶点
        boolean[] visited = new boolean[vertexCount];
        // 初始化minDistances数组，从第一个顶点开始访问
        Arrays.fill(minDistances, INF);
        minDistances[0] = 0;

        // 存储每个访问过的顶点的下标
        int[] visitedVertexes = new int[vertexCount];
        // 初始化visitedVertexes数组，从第一个顶点开始访问
        visitedVertexes[0] = 0;

        // 访问剩余的vertexCount-1个顶点
        for (int i = 1; i < vertexCount; i++) {
            // 从未访问过的顶点中选取一个距离最近的顶点
            int minDistance = INF;
            int minIndex = -1;
            for (int j = 0; j < vertexCount; j++) {
                if (!visited[j] && minDistances[j] < minDistance) {
                    minDistance = minDistances[j];
                    minIndex = j;
                }
            }

            // 标记这个顶点已经访问过了
            visited[minIndex] = true;
            // 将这个顶点加入visitedVertexes数组中，表示已经访问过了
            visitedVertexes[i] = minIndex;

            // 更新minDistances数组
            for (int j = 0; j < vertexCount; j++) {
                if (!visited[j] && weightMatrix[minIndex][j] < minDistances[j]) {
                    minDistances[j] = weightMatrix[minIndex][j];
                }
            }
        }

        // 输出最小生成树
        System.out.println("最小生成树的边：");
        for (int i = 1; i < vertexCount; i++) {
            int start = visitedVertexes[i - 1];
            int end = visitedVertexes[i];
            System.out.println(vertexData[start] + " - " + vertexData[end] + " : " + weightMatrix[start][end]);
        }
    }

    public static void main(String[] args) {
        char[] vertexData = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        int[][] weightMatrix = {
                {0, 5, INF, INF, INF, 7, INF},
                {5, 0, 7, INF, INF, INF, INF},
                {INF, 7, 0, 9, INF, INF, INF},
                {INF, INF, 9, 0, INF, 5, INF},
                {INF, INF, INF, INF, 0, INF, 6},
                {7, INF, INF, 5, INF, 0, 8},
                {INF, INF, INF, INF, 6, 8, 0}
        };

        PrimAlgorithm primAlgorithm = new PrimAlgorithm(vertexData, weightMatrix);
        primAlgorithm.prim();
    }
}

以上代码实现了Prim算法的主要逻辑，可以通过给定的顶点数据和权重矩阵来求解最小生成树。