JavaにおけるPrimeアルゴリズムの原理と実装（概要共有）-＆＃＆チュートリアル-php.cn

この記事では、java に関する関連知識を提供します。Prime アルゴリズムは、接続されたグラフから最小スパニングツリーを構築するための徹底的な検索アルゴリズムです。この記事では主にJavaにおけるPrimeアルゴリズムの原理と実装について紹介しますので、興味のある方はぜひ学んでみてください。

JavaにおけるPrimeアルゴリズムの原理と実装（概要共有）

## 推奨学習: 「

Java ビデオチュートリアル」

Prim アルゴリズムの概要

#1. 最後の仕上げ

ツリーを生成する過程では、スパニングツリーにすでに存在するノードを集合とみなし、残りのノードを別の集合とみなし、両者を結ぶエッジの中から最も重みの小さいエッジを選択します。セットできます。

2. アルゴリズムの紹介

最初にノード 1 などのノードを選択し、それをセット U、U={1} に入れます。残りのノードは V-U={2,3,4,5,6,7} であり、集合 V はグラフのすべてのノードの集合です。

ここで必要なのは、2 つのセット (U および V-U) を接続するエッジの中でどのエッジが最小の重みを持つかを確認し、そのノードを最小のエッジに関連付けることだけです。 Uを設定します。上図からわかるように、2 つのセットを接続する 3 つのエッジのうち、最も重みが小さいエッジ 1-2 を選択し、セット U, U={1,2}, V - U= にノード 2 を追加します。以下の図に示すように、{ 3,4,5,6}。

次に、2 つのセット (U と V-U) を接続するエッジから最小の重みを持つエッジを選択します。上図からわかるように、2 つのセットを接続する 4 つのエッジのうち、ノード 2 からノード 7 までのエッジの重みが最も小さいので、このエッジを選択し、セット U={1,2,7} にノード 7 を追加します。、V-U ={3,4,5,6}。

これは U=V が終了するまで続き、選択されたエッジとすべてのノードから構成されるグラフが最小全域木になります。これがプリムのアルゴリズムです。

グラフを直感的に見ると、集合 U から集合 U-V までのどのエッジが最も重みが小さいかを見つけるのは簡単ですが、プログラム内でこれらのエッジを網羅的に列挙してから実行するのは時間がかかります。最小値を求める次数が高すぎます。この問題は配列を設定することで賢く解決できます Closet[j] は集合 V-U のノード j から集合 U への最近傍点を表します Lowcost[j] は集合 V-U のノード j から集合 U への最近傍点のエッジ値を表しますset U。つまり、エッジの重み (j,most[j])。

たとえば、上の図では、ノード 7 からセット U への最近傍点は 2 (cloeest[7]=2) です。ノード 7 から最近傍点 2 までのエッジ値は 1 で、これはエッジ (2,7) の重みであり、次の図に示すように lowcost[7]=1 として記録されます。

したがって、集合 V - U 内の最小のノード lowcost[] を見つけるだけです。

3. アルゴリズムの手順

1. 初期化

セット U={u0}、u0 を V に属させ、配列最も近い[]、低コスト[]を初期化します。そしてs[]。

2. 集合 V-U 内で最小の lowcost 値を持つノード t、つまり lowcost[t]=min{lowcost[j]}、j が V-U に属するノード t を見つけます。この式を満たすノード t は集合 V-U の接続 U は最近点です。

3. ノード t を集合 U に追加します。

4. セット V - U が空の場合、アルゴリズムは終了し、そうでない場合はステップ 5 に進みます。

5. セット V-U 内のすべてのノード j の lowcost[] と Closest[] を更新します。 if(C[t][j]上記の手順に従って、最終的に重みの合計が最小のスパニングツリーを取得できます。

4. 図

グラフ G=(V,E) は、以下の図に示すように、無向連結重み付きグラフです。

#1 初期化。 u0=1 と仮定し、セット U={1}、セット V-U={2,3,4,5,6,7}、s[1]=true として、配列最も近い [] を初期化します: ノード 1 を除く、他のすべてのノードは 1 です。これは、セット V-U 内のノードからセット U までの最も近い隣接点がすべて 1 であることを意味します。 lowcost[]: セット V-U 内のノード 1 からノードまでのエッジ値。以下の図に、closest[] と lowcost[] を示します。

初期化後の画像は次のとおりです:

2 t=2 に対応する最小の低コストのノードを見つけます。選択されたエッジとノードは次のようになります。

#3 セット U に追加します。ノード t を集合 U、U={1,2} に追加し、同時に V-U={3,4,5,6,7}

4 を更新します。集合 V-U 内の t の各隣接点 j について、t を使用して更新できます。ノード 2 の隣接ポイントはノード 3 とノード 7 です。

C[2][3]=20

C[ 2][7]=1

closed[] と lowcost[] を次のように更新しました下に示された。

更新されたセットは以下のとおりです:

5 最小の低コストのノードを見つけ、それに対応するt= 7。選択されたエッジとノードは次のようになります。

#6 セット U に追加します。ノード t を集合 U、U={1,2,7} に追加し、同時に V-U={3,4,5,6}

7 を更新します。集合 V-U 内の t の各隣接点 j について、t を使用して更新できます。ノード 7 の隣接点はノード 3、4、5、および 6 です。

C[7][3]=4
C[7][4]=4
C[7 ][5 ]=4
C[7][6]=4

更新された最近傍[]とlowcost[]は以下に示すとおりです。

#更新されたセットを以下の図に示します。

##8 最小の低コストのノードを見つけます。 t= 3 に対応します。選択されたエッジとノードは次のようになります。

9 セット U に追加します。ノード t を集合 U、U={1,2,3,7} に追加し、同時に V-U={4,5,6}

10 を更新します。集合 V-U 内の t の各隣接点 j について、t を使用して更新できます。ノード 3 の隣接ノードはノード 4 です。

C[3][4]=15>lowcost[4]=9、更新なし

closest[] 配列と lowcost[] 配列は変更されません。

更新されたセットは次のとおりです。

#11 t=4 に対応する最小の低コストのノードと選択されたエッジを見つけます。ノードは以下のようになります。

12 セット U に追加します。ノード t を集合 U、U={1,2,3,4,7} に追加し、同時に V-U={5,6}

13 を更新します。集合 V-U 内の t の各隣接点 j について、t を使用して更新できます。ノード 4 の隣接ノードはノード 5 です。

C[4][5]=3

更新された以下の図に、closest[] と lowcost[] を示します。

#更新されたセットは次のとおりです:

#14 最小の低コストを持つノードと、対応する t を見つけます。 = 5. 選択されたエッジとノードは次のようになります。

15 セット U に追加します。ノード t を集合 U、U={1,2,3,4,5,7} に追加し、同時に V-U={6}

16 を更新します。集合 V-U 内の t の各隣接点 j について、t を使用して更新できます。ノード 5 の隣接ノードはノード 6 です。

C[5][6]=17

Updated セットは次のとおりです

17 t=6 に対応する最小の低コストのノードを見つけます。選択されたエッジとノードは次のようになります。

18 セット U に追加します。ノード t を集合 U、U={1,2,3,4,5,6,7} に追加し、同時に V-U={}

19 を更新します。集合 V-U 内の t の各隣接点 j について、t を使用して更新できます。ノード 6 には、セット V-U 内に隣接する点がありません。 Closest[] と lowcost[] を更新する必要はありません。

20 得られた最小全域木は以下の通りです。最小スパニングツリーの重みの合計は 57.

プライムアルゴリズムの実装

#1. 構築されたグラフ

#2. コード

package graph.prim;
 
import java.util.Scanner;
 
public class Prim {
    static final int INF = 0x3f3f3f3f;
    static final int N = 100;
    // 如果s[i]=true,说明顶点i已加入U
    static boolean s[] = new boolean[N];
    static int c[][] = new int[N][N];
    static int closest[] = new int[N];
    static int lowcost[] = new int[N];
 
    static void Prim(int n) {
        // 初始时，集合中 U 只有一个元素，即顶点 1
        s[1] = true;
        for (int i = 1; i <= n; i++) {
            if (i != 1) {
                lowcost[i] = c[1][i];
                closest[i] = 1;
                s[i] = false;
            } else
                lowcost[i] = 0;
        }
        for (int i = 1; i < n; i++) {
            int temp = INF;
            int t = 1;
            // 在集合中 V-u 中寻找距离集合U最近的顶点t
            for (int j = 1; j <= n; j++) {
                if (!s[j] && lowcost[j] < temp) {
                    t = j;
                    temp = lowcost[j];
                }
            }
            if (t == 1)
                break; // 找不到 t，跳出循环
            s[t] = true; // 否则，t 加入集合U
            for (int j = 1; j <= n; j++) { // 更新 lowcost 和 closest
                if (!s[j] && c[t][j] < lowcost[j]) {
                    lowcost[j] = c[t][j];
                    closest[j] = t;
                }
            }
        }
    }
 
    public static void main(String[] args) {
        int n, m, u, v, w;
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        m = scanner.nextInt();
        int sumcost = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                c[i][j] = INF;
        for (int i = 1; i <= m; i++) {
            u = scanner.nextInt();
            v = scanner.nextInt();
            w = scanner.nextInt();
            c[u][v] = c[v][u] = w;
        }
        Prim(n);
        System.out.println("数组lowcost:");
 
        for (int i = 1; i <= n; i++)
            System.out.print(lowcost[i] + " ");
 
        System.out.println();
        for (int i = 1; i <= n; i++)
            sumcost += lowcost[i];
        System.out.println("最小的花费：" + sumcost);
    }
}

ログイン後にコピー

3. テスト