Javaを使用してPrimのアルゴリズムを実装する方法

Java を使用して Prim のアルゴリズムを実装する方法

Prim アルゴリズムは、最小スパニング ツリーを解決するための古典的なアルゴリズムであり、さまざまなネットワーク最適化問題の解決に使用できます。この記事では、Java 言語を使用して Prim のアルゴリズムを実装する方法と、対応するコード例を紹介します。

1. アルゴリズムのアイデア
   Prim アルゴリズムの基本的なアイデアは、最初の頂点から開始し、徐々に拡張して最小スパニング ツリーを生成することです。具体的な手順は次のとおりです。

1) 最小スパニング ツリーを空に初期化し、初期頂点 v を選択して最小スパニング ツリー セットに参加させます。
2) 最小スパニング ツリー セットにすべての頂点が含まれるまで、次の手順をループで実行します。
a) 頂点に対する u の重みが最小になるように、最小スパニング ツリー セットの外側から頂点 u を選択します。スパニングツリーセットは最小です。
b) 頂点 u を最小スパニング ツリー セットに追加し、エッジ (u、v) の重みを記録します。
c) u の重みを最小スパニングツリーセット外の頂点に更新する 頂点の重みが小さい場合は、頂点の重みを最小スパニングツリーセット内の頂点に更新します。

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

上記のコードでは、隣接行列を使用して次のことを行います。グラフを表し、ダイクストラのアルゴリズムを使用して最小スパニング ツリーの合計重みを見つけます。この例では、アルゴリズムの使用法を示すために 5 頂点のグラフを使用します。

3. 概要
   この記事の導入部を通じて、Prim のアルゴリズムの基本的な考え方と、Java 言語を使用してアルゴリズムを実装する方法を理解しました。この記事が、読者が Prim のアルゴリズムをより深く理解し、実際のアプリケーションで柔軟に使用できるようになることを願っています。

以上がJavaを使用してPrimのアルゴリズムを実装する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。