Java를 사용하여 Prim의 알고리즘을 구현하는 방법-java지도 시간-php.cn

Java를 사용하여 Prim의 알고리즘을 구현하는 방법

王林

풀어 주다： 2023-09-20 09:06:25

원래의

821명이 탐색했습니다.

Java를 사용하여 Prim의 알고리즘을 구현하는 방법

Prim의 알고리즘은 최소 신장 트리를 해결하기 위한 고전적인 알고리즘으로 다양한 네트워크 최적화 문제를 해결하는 데 사용할 수 있습니다. 본 글에서는 Java 언어를 사용하여 Prim의 알고리즘을 구현하는 방법을 소개하고 해당 코드 예제를 제공합니다.

알고리즘 아이디어
프림 알고리즘의 기본 아이디어는 초기 정점에서 시작하여 점차 확장하여 최소 스패닝 트리를 생성하는 것입니다. 구체적인 단계는 다음과 같습니다.

1) 최소 스패닝 트리를 비우도록 초기화하고 초기 정점 v를 선택하여 최소 스패닝 트리 세트에 합류합니다.
2) 최소 스패닝 트리 집합에 모든 정점이 포함될 때까지 루프에서 다음 단계를 수행합니다.
a) 최소 스패닝 트리 집합의 정점에 대한 u의 가중치가 다음과 같도록 최소 스패닝 트리 집합 외부에서 정점 u를 선택합니다. 가장 작은.
b) 최소 스패닝 트리 집합에 정점 u를 추가하고 가장자리의 가중치(u, v)를 기록합니다.
c) u의 가중치를 최소 스패닝 트리 집합 외부의 정점으로 업데이트합니다. 정점의 가중치가 더 작은 경우 정점의 가중치를 최소 스패닝 트리 집합의 정점으로 업데이트합니다.

Java 코드 구현
다음은 Java 언어를 사용하여 Prim의 알고리즘을 구현한 코드 예제입니다.

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);
    }
}

로그인 후 복사

위 코드에서는 인접 행렬을 사용하여 그래프를 표현하고 Dijkstra의 알고리즘을 사용하여 총 가중치를 해결합니다. 최소 스패닝 트리. 이 예에서는 알고리즘의 사용법을 보여주기 위해 5개의 꼭지점 그래프를 사용합니다.