Code Java pour implémenter l'algorithme de Kruskal

L'algorithme de Kruskal

L'algorithme de Kruskal est un algorithme glouton utilisé pour résoudre le problème de l'arbre couvrant minimum. Un arbre couvrant minimum est un arbre couvrant avec la plus petite somme de poids d'arêtes dans un graphe non orienté connecté. L'algorithme de Kruskal sélectionne les arêtes dans l'ordre de poids d'arête petit à grand. Lorsque les arêtes sélectionnées ne forment pas un cycle, elles sont ajoutées à l'arbre couvrant. Le processus spécifique de mise en œuvre est le suivant :

• Triez toutes les arêtes de petite à grande en fonction de leurs poids d'arête.

• Sélectionnez les arêtes à tour de rôle. Si les deux extrémités de l'arête sélectionnée ne sont pas dans le même composant connecté, ajoutez cette arête à l'arbre couvrant minimum et fusionnez les deux extrémités dans le même composant connecté.

• Jusqu'à ce que l'arbre couvrant minimum contienne tous les sommets du graphique. L'avantage de l'algorithme

est qu'il doit uniquement prêter attention au poids du bord et n'a rien à voir avec le degré du sommet, il peut donc également afficher de meilleures performances dans les graphiques denses. Dans le même temps, l'algorithme de Kruskal a également une bonne évolutivité et peut facilement gérer le problème de forêt couvrante minimale dans les graphiques pondérés.

Processus d'exécution

• Triez toutes les arêtes en fonction de leur poids, de petit à grand ;

• Traversez chaque arête tour à tour Si les deux nœuds connectés par cette arête ne sont pas dans le même composant connecté, alors ajoutez l'arête. au spanning tree et fusionnez les deux nœuds en un composant connecté ;

• Répétez l'étape 2 jusqu'à ce que tous les nœuds soient dans le même composant connecté et que l'arbre généré à ce moment soit le spanning tree minimum.

Pendant le processus de mise en œuvre, la recherche d'union est généralement utilisée pour maintenir la connectivité afin d'améliorer l'efficacité.

Implémentation du code

import java.util.*;

public class KruskalAlgorithm {
    
    // 定义边的数据结构
    class Edge implements Comparable<Edge> {
        int src, dest, weight;
 
        public int compareTo(Edge edge) {
            return this.weight - edge.weight;
        }
    }
    
    // 并查集数据结构
    class Subset {
        int parent, rank;
    }
 
    int V, E; // V是顶点数，E是边数
    Edge edge[]; // 存储边的数组
 
    // 构造函数，初始化边和顶点数
    KruskalAlgorithm(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }
 
    // 查找父节点
    int find(Subset subsets[], int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }
 
    // 合并两个子集
    void union(Subset subsets[], int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);
 
        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }
 
    // 执行克鲁斯卡尔算法
    void kruskal() {
        Edge result[] = new Edge[V]; // 存储结果的数组
        int e = 0; // 表示result数组中的下标
 
        // 将边按照权重从小到大排序
        Arrays.sort(edge);
 
        // 创建V个子集
        Subset subsets[] = new Subset[V];
        for (int i = 0; i < V; ++i)
            subsets[i] = new Subset();
 
        // 初始化每个子集的父节点和秩
        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }
 
        // 取E-1条边
        int i = 0;
        while (e < V - 1) {
            Edge next_edge = new Edge();
            next_edge = edge[i++];
 
            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);
 
            // 如果两个节点不在同一个集合中，合并它们
            if (x != y) {
                result[e++] = next_edge;
                union(subsets, x, y);
            }
        }
 
        // 打印结果
        System.out.println("Following are the edges in the constructed MST");
        for (i = 0; i < e; ++i){
            System.out.println(result[i].src + " - " + result[i" - " + result[i].weight);
            return;
        }
        
        // 定义一个辅助函数，用于查找结点所在的集合 
        private int find(int parent[], int i) { 
            if (parent[i] == -1) 
                return i; 
            return find(parent, parent[i]); 
        }

        // 定义一个辅助函数，用于合并两个集合 
        private void union(int parent[], int x, int y) { 
            int xset = find(parent, x); 
            int yset = find(parent, y); 
            parent[xset] = yset; 
        } 
    }
}

La fonction utilise la méthode de tri de la classe Arrays pour trier les bords en fonction de leur poids de petit à grand. Ensuite, la fonction parcourt les arêtes triées en séquence et, pour chaque arête, utilise la fonction find pour trouver le nœud racine de l'ensemble où se trouvent son src et sa destination. Si les nœuds racines sont différents, cela signifie que les deux ensembles ne sont pas connectés et peuvent être fusionnés, et les arêtes sont ajoutées au tableau de résultats de l'arbre couvrant minimum. Enfin, la fonction parcourt le tableau de résultats de l'arbre couvrant minimum et génère le point de départ, le point final et le poids de chaque arête.

Dans cette implémentation, une méthode de recherche rapide d'ensembles est utilisée, c'est-à-dire utiliser la recherche par union pour y parvenir. Chaque nœud a un tableau parent, où parent[i] représente le nœud parent du nœud i. Si parent[i] == -1, le nœud i est le nœud racine. Lors de la recherche de l'ensemble où se trouve le nœud, si le nœud parent du nœud actuel est -1, cela signifie que le nœud est le nœud racine et est renvoyé directement sinon, l'ensemble où se trouve le nœud parent est recherché de manière récursive ; . Lors de la fusion de deux collections, recherchez les nœuds racine des deux collections à fusionner et définissez le nœud parent d'un nœud racine sur l'index de l'autre nœud racine, c'est-à-dire fusionnez le nœud racine d'une collection sous le nœud racine de l'autre recueil.

La complexité temporelle de l'algorithme de Kruskal implémenté de cette manière est O(ElogE), où E représente le nombre d'arêtes dans le graphique. Le principal coût en temps réside dans le processus de tri des arêtes. La complexité spatiale est O(V+E), où V représente le nombre de sommets dans le graphe. La principale surcharge spatiale consiste à stocker les arêtes et les tableaux parents.

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!