Comment implémenter l'algorithme de Prim en utilisant Java

Comment utiliser Java pour implémenter l'algorithme de Prim

L'algorithme de Prim est un algorithme classique pour résoudre les arbres couvrants minimaux et peut être utilisé pour résoudre divers problèmes d'optimisation de réseau. Dans cet article, nous présenterons comment implémenter l'algorithme de Prim à l'aide du langage Java et fournirons des exemples de code correspondants.

1. Idée d'algorithme
   L'idée de base de l'algorithme de Prim est de partir d'un sommet initial et de s'étendre progressivement pour générer un arbre couvrant minimum. Les étapes spécifiques sont les suivantes :

1) Initialisez l'arbre couvrant minimum pour qu'il soit vide, sélectionnez un sommet initial v pour rejoindre l'ensemble d'arbre couvrant minimum.
2) Effectuez les étapes suivantes en boucle jusqu'à ce que l'ensemble minimal d'arbres couvrants contienne tous les sommets :
a) Sélectionnez un sommet u à l'extérieur de l'ensemble minimal d'arbres couvrants de telle sorte que le poids de u au sommet dans l'ensemble minimal d'arbres couvrants soit le plus petit.
b) Ajoutez le sommet u à l'ensemble minimal d'arbre couvrant et enregistrez les poids des arêtes (u, v).
c) Mettez à jour le poids de u au sommet en dehors de l'ensemble d'arbre couvrant minimum. Si le poids d'un sommet est plus petit, mettez à jour le poids du sommet au sommet dans l'ensemble d'arbre couvrant minimum.

2. Implémentation du code Java
   Ce qui suit est un exemple de code utilisant le langage Java pour implémenter l'algorithme de 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);
    }
}

Dans le code ci-dessus, nous utilisons la matrice d'adjacence pour représenter le graphique et utilisons l'algorithme de Dijkstra pour résoudre le poids total de l'arbre couvrant minimum. Dans l'exemple, nous utilisons un graphe à 5 sommets pour démontrer l'utilisation de l'algorithme.

3. Résumé
   Grâce à l'introduction de cet article, nous comprenons l'idée de base de l'algorithme de Prim et comment implémenter l'algorithme en utilisant le langage Java. J'espère que cet article pourra aider les lecteurs à mieux comprendre l'algorithme de Prim et à pouvoir l'utiliser de manière flexible dans des applications pratiques.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!