Les Algorithmes de Prim et Kruskal

Introduction

Les algorithmes de Prim et Kruskal sont des algorithmes utilisés pour trouver un arbre de recouvrement minimal (MST, Minimum Spanning Tree) dans un graphe pondéré. Un MST est un sous-ensemble des arêtes d'un graphe qui connecte tous les sommets ensemble, sans cycles, et avec le poids total minimal.

Algorithme de Prim

L'algorithme de Prim construit le MST en ajoutant progressivement les arêtes de poids minimal qui relient un sommet à l'ensemble déjà construit.

Étapes de l'algorithme de Prim :

1. Initialisation :

   • Commencez par un sommet arbitraire.
   • Marquez ce sommet comme visité.
   • Ajoutez toutes les arêtes sortantes de ce sommet dans une file de priorité (généralement un tas).

2. Construction de l'arbre :

   • Sélectionnez l'arête de poids minimal à partir de la file de priorité.
   • Ajoutez cette arête à l'arbre de recouvrement si elle connecte un sommet visité à un sommet non visité.
   • Marquez le nouveau sommet comme visité.
   • Ajoutez toutes les nouvelles arêtes sortantes de ce sommet à la file de priorité.

3. Répétez :

   • Continuez jusqu'à ce que tous les sommets soient visités.

Implémentation en JavaScript

class MinHeap {
    // Constructeur initialisant le tableau du tas
    constructor() {
        this.heap = []; // Le tas est initialement vide
    }

    // Méthode pour insérer un élément dans le tas
    insert(key, value) {
        // Ajoute le nouvel élément à la fin du tableau
        this.heap.push({ key, value });
        // Appelle la méthode bubbleUp pour restaurer la propriété du tas
        this.bubbleUp();
    }

    // Méthode pour extraire l'élément minimal (racine) du tas
    extractMin() {
        // Si le tas est vide, retourne null
        if (this.heap.length === 0) return null;
        // Sauvegarde la racine du tas (l'élément minimal)
        const min = this.heap[0];
        // Prend le dernier élément du tas
        const end = this.heap.pop();
        // Si le tas n'est pas vide, place le dernier élément à la racine et appelle sinkDown
        if (this.heap.length > 0) {
            this.heap[0] = end;
            this.sinkDown(0);
        }
        // Retourne l'élément minimal
        return min;
    }

    // Méthode pour restaurer la propriété du tas en remontant un élément
    bubbleUp() {
        let index = this.heap.length - 1; // Commence par le dernier élément
        const element = this.heap[index]; // L'élément à remonter
        // Continue jusqu'à ce que l'élément soit à la bonne place
        while (index > 0) {
            let parentIndex = Math.floor((index - 1) / 2); // Trouve l'index du parent
            let parent = this.heap[parentIndex]; // L'élément parent
            // Si l'élément est plus grand ou égal au parent, arrête
            if (element.value >= parent.value) break;
            // Échange l'élément avec son parent
            this.heap[index] = parent;
            index = parentIndex;
        }
        // Place l'élément à sa position correcte
        this.heap[index] = element;
    }

    // Méthode pour restaurer la propriété du tas en descendant un élément
    sinkDown(index) {
        const length = this.heap.length; // Longueur du tas
        const element = this.heap[index]; // L'élément à descendre
        while (true) {
            let leftChildIndex = 2 * index + 1; // Index du fils gauche
            let rightChildIndex = 2 * index + 2; // Index du fils droit
            let leftChild, rightChild; // Fils gauche et droit
            let swap = null; // Index de l'élément avec lequel échanger

            // Si le fils gauche existe et est plus petit que l'élément
            if (leftChildIndex < length) {
                leftChild = this.heap[leftChildIndex];
                if (leftChild.value < element.value) swap = leftChildIndex;
            }

            // Si le fils droit existe et est plus petit que l'élément ou le fils gauche
            if (rightChildIndex < length) {
                rightChild = this.heap[rightChildIndex];
                if ((swap === null && rightChild.value < element.value) || 
                    (swap !== null && rightChild.value < leftChild.value)) {
                    swap = rightChildIndex;
                }
            }

            // Si aucun échange n'est nécessaire, arrête
            if (swap === null) break;
            // Échange l'élément avec l'élément enfant
            this.heap[index] = this.heap[swap];
            index = swap;
        }
        // Place l'élément à sa position correcte
        this.heap[index] = element;
    }
}

function prim(graph, start) {
    const mst = []; // Liste pour stocker les arêtes de l'arbre de recouvrement minimal
    const visited = new Set(); // Ensemble pour suivre les sommets visités
    const minHeap = new MinHeap(); // Création du tas minimum

    // Insère le sommet de départ dans le tas avec un poids de 0
    minHeap.insert(start, 0);

    // Tant que le tas n'est pas vide
    while (minHeap.heap.length > 0) {
        // Extrait l'élément minimal du tas
        const { key: node, value: weight } = minHeap.extractMin();

        // Si le sommet a déjà été visité, continue à la prochaine itération
        if (visited.has(node)) continue;
        // Marque le sommet comme visité
        visited.add(node);

        // Si le sommet n'est pas le sommet de départ, ajoute l'arête au MST
        if (node !== start) mst.push({ node, weight });

        // Pour chaque voisin du sommet actuel
        graph[node].forEach(({ neighbor, weight }) => {
            // Si le voisin n'a pas été visité, l'insère dans le tas
            if (!visited.has(neighbor)) {
                minHeap.insert(neighbor, weight);
            }
        });
    }

    // Retourne l'arbre de recouvrement minimal
    return mst;
}

// Définition du graphe sous forme de liste d'adjacence
const graph = {
    0: [{ neighbor: 1, weight: 4 }, { neighbor: 7, weight: 8 }], // Arêtes connectant le sommet 0 aux sommets 1 et 7
    1: [{ neighbor: 0, weight: 4 }, { neighbor: 2, weight: 8 }, { neighbor: 7, weight: 11 }], // Arêtes connectant le sommet 1 aux sommets 0, 2 et 7
    2: [{ neighbor: 1, weight: 8 }, { neighbor: 3, weight: 7 }, { neighbor: 5, weight: 4 }, { neighbor: 8, weight: 2 }], // Arêtes connectant le sommet 2 aux sommets 1, 3, 5 et 8
    3: [{ neighbor: 2, weight: 7 }, { neighbor: 4, weight: 9 }, { neighbor: 5, weight: 14 }], // Arêtes connectant le sommet 3 aux sommets 2, 4 et 5
    4: [{ neighbor: 3, weight: 9 }, { neighbor: 5, weight: 10 }], // Arêtes connectant le sommet 4 aux sommets 3 et 5
    5: [{ neighbor: 2, weight: 4 }, { neighbor: 3, weight: 14 }, { neighbor: 4, weight: 10 }, { neighbor: 6, weight: 2 }], // Arêtes connectant le sommet 5 aux sommets 2, 3, 4 et 6
    6: [{ neighbor: 5, weight: 2 }, { neighbor: 7, weight: 1 }, { neighbor: 8, weight: 6 }], // Arêtes connectant le sommet 6 aux sommets 5, 7 et 8
    7: [{ neighbor: 0, weight: 8 }, { neighbor: 1, weight: 11 }, { neighbor: 6, weight: 1 }, { neighbor: 8, weight: 7 }], // Arêtes connectant le sommet 7 aux sommets 0, 1, 6 et 8
    8: [{ neighbor: 2, weight: 2 }, { neighbor: 6, weight: 6 }, { neighbor: 7, weight: 7 }] // Arêtes connectant le sommet 8 aux sommets 2, 6 et 7
};

// Exécute l'algorithme de Prim sur le graphe avec le sommet de départ 0 et obtient l'arbre de recouvrement minimal
const mst = prim(graph, 0);
console.log(mst); // Affiche l'arbre de recouvrement minimal

  Explication du Code de Prim

1. 1. Classe MinHeap : Une classe de tas minimum utilisée pour extraire la prochaine arête de poids minimal.
   2. Fonction prim :
      • Initialise la MST et les ensembles de sommets visités.
      • Insère le sommet de départ dans le tas.
      • Répète l'extraction du tas et ajoute les arêtes de poids minimal à la MST.
      • Retourne le MST.

Algorithme de Kruskal

L'algorithme de Kruskal construit le MST en ajoutant progressivement les arêtes de poids minimal qui ne forment pas de cycles, en utilisant une structure de données d'union-find.

Étapes de l'algorithme de Kruskal :

1. Initialisation :

   • Classez toutes les arêtes par ordre croissant de poids.

2. Construction de l'arbre :

   • Ajoutez les arêtes de poids minimal au MST, une à la fois, en utilisant une structure d'union-find pour éviter les cycles.

3. Répétez :

   • Continuez jusqu'à ce que le MST soit complet (c'est-à-dire qu'il contienne V-1 arêtes, où V est le nombre de sommets).

Implémentation en JavaScript

class UnionFind {
    // Constructeur initialisant les tableaux parent et rank
    constructor(size) {
        // Le tableau parent garde une référence au parent de chaque noeud, initialement chaque noeud est son propre parent
        this.parent = new Array(size).fill(null).map((_, index) => index);
        // Le tableau rank garde la profondeur de chaque arbre, initialement 0
        this.rank = new Array(size).fill(0);
    }

    // Méthode pour trouver la racine d'un noeud avec compression de chemin
    find(node) {
        // Si le noeud n'est pas son propre parent, applique la compression de chemin
        if (this.parent[node] !== node) {
            // La compression de chemin : met à jour le parent de chaque noeud pour qu'il pointe directement sur la racine
            this.parent[node] = this.find(this.parent[node]);
        }
        // Retourne le parent (racine) du noeud
        return this.parent[node];
    }

    // Méthode pour unir deux ensembles
    union(node1, node2) {
        // Trouve les racines des deux noeuds
        const root1 = this.find(node1);
        const root2 = this.find(node2);

        // Si les racines sont différentes, unir les deux ensembles
        if (root1 !== root2) {
            // Compare les rangs pour décider quelle racine doit devenir le parent de l'autre
            if (this.rank[root1] > this.rank[root2]) {
                // Si le rang de root1 est plus grand, root2 devient enfant de root1
                this.parent[root2] = root1;
            } else if (this.rank[root1] < this.rank[root2]) {
                // Si le rang de root2 est plus grand, root1 devient enfant de root2
                this.parent[root1] = root2;
            } else {
                // Si les rangs sont égaux, fait de root1 le parent de root2 et augmente le rang de root1
                this.parent[root2] = root1;
                this.rank[root1]++;
            }
        }
    }
}

function kruskal(graph) {
    const edges = []; // Liste pour stocker toutes les arêtes du graphe

    // Parcourt chaque noeud du graphe
    for (let node in graph) {
        // Parcourt chaque voisin du noeud actuel
        for (let { neighbor, weight } of graph[node]) {
            // Ajoute l'arête à la liste des arêtes
            edges.push({ node1: parseInt(node), node2: neighbor, weight });
        }
    }

    // Trie les arêtes par poids croissant
    edges.sort((a, b) => a.weight - b.weight);

    // Crée une instance de la classe UnionFind
    const uf = new UnionFind(Object.keys(graph).length);
    const mst = []; // Liste pour stocker les arêtes de l'arbre de recouvrement minimal

    // Parcourt chaque arête triée
    for (let { node1, node2, weight } of edges) {
        // Si les deux noeuds de l'arête n'ont pas la même racine, ils appartiennent à des composants différents
        if (uf.find(node1) !== uf.find(node2)) {
            // Unir les deux composants
            uf.union(node1, node2);
            // Ajouter l'arête à l'arbre de recouvrement minimal
            mst.push({ node1, node2, weight });
        }
    }

    // Retourne l'arbre de recouvrement minimal
    return mst;
}

const graph = {
    0: [{ neighbor: 1, weight: 4 }, { neighbor: 7, weight: 8 }], // Noeud 0 connecté à 1 (poids 4) et à 7 (poids 8)
    1: [{ neighbor: 0, weight: 4 }, { neighbor: 2, weight: 8 }, { neighbor: 7, weight: 11 }], // Noeud 1 connecté à 0, 2 et 7
    2: [{ neighbor: 1, weight: 8 }, { neighbor: 3, weight: 7 }, { neighbor: 5, weight: 4 }, { neighbor: 8, weight: 2 }], // Noeud 2 connecté à 1, 3, 5 et 8
    3: [{ neighbor: 2, weight: 7 }, { neighbor: 4, weight: 9 }, { neighbor: 5, weight: 14 }], // Noeud 3 connecté à 2, 4 et 5
    4: [{ neighbor: 3, weight: 9 }, { neighbor: 5, weight: 10 }], // Noeud 4 connecté à 3 et 5
    5: [{ neighbor: 2, weight: 4 }, { neighbor: 3, weight: 14 }, { neighbor: 4, weight: 10 }, { neighbor: 6, weight: 2 }], // Noeud 5 connecté à 2, 3, 4 et 6
    6: [{ neighbor: 5, weight: 2 }, { neighbor: 7, weight: 1 }, { neighbor: 8, weight: 6 }], // Noeud 6 connecté à 5, 7 et 8
    7: [{ neighbor: 0, weight: 8 }, { neighbor: 1, weight: 11 }, { neighbor: 6, weight: 1 }, { neighbor: 8, weight: 7 }], // Noeud 7 connecté à 0, 1, 6 et 8
    8: [{ neighbor: 2, weight: 2 }, { neighbor: 6, weight: 6 }, { neighbor: 7, weight: 7 }] // Noeud 8 connecté à 2, 6 et 7
};

// Exécute l'algorithme de Kruskal sur le graphe et obtient l'arbre de recouvrement minimal
const mst = kruskal(graph);
console.log(mst); // Affiche l'arbre de recouvrement minimal

Explication du Code de Kruskal

1. Classe UnionFind : Une structure de données pour gérer les ensembles disjoints et détecter les cycles.
2. Fonction kruskal :
   • Construit une liste de toutes les arêtes et les trie par ordre croissant de poids.
   • Utilise l'union-find pour ajouter les arêtes de poids minimal au MST, tout en évitant les cycles.
   • Retourne le MST.

Cas Réels d'Utilisation des Algorithmes de Prim et Kruskal

Les algorithmes de Prim et Kruskal sont utilisés dans diverses applications pratiques, en particulier dans les domaines des réseaux, de la gestion des ressources et de la planification. Voici quelques exemples concrets de leur utilisation :

1. Conception de Réseaux

Problème : Concevoir un réseau de communication (comme Internet, les réseaux de télécommunications ou les réseaux électriques) avec le coût total le plus bas possible.

• Application de Prim et Kruskal : Les deux algorithmes peuvent être utilisés pour déterminer l'arbre de recouvrement minimal qui représente le réseau de connexion entre les différents nœuds (ordinateurs, serveurs, stations de télécommunications) avec le coût minimal. Par exemple, pour un réseau électrique, ces algorithmes peuvent aider à minimiser le coût total de câblage en s'assurant que chaque station est connectée avec le moins de fil possible.

2. Transport et Logistique

Problème : Optimiser les routes de transport pour minimiser les coûts de carburant et de temps.

• Application de Prim et Kruskal : Dans la gestion de la logistique et des transports, ces algorithmes peuvent être utilisés pour planifier les itinéraires de livraison de manière à minimiser les coûts de transport. Par exemple, une entreprise de livraison peut utiliser ces algorithmes pour s'assurer que tous les points de livraison sont connectés de manière optimale, réduisant ainsi les distances parcourues et les coûts de carburant.

3. Réseaux Sociaux

Problème : Analyser les connexions entre les utilisateurs pour trouver les groupes les plus fortement connectés ou les chemins de connexion les plus courts.

• Application de Prim et Kruskal : Dans l'analyse des réseaux sociaux, ces algorithmes peuvent aider à identifier les groupes d'utilisateurs les plus fortement connectés ou à recommander de nouvelles connexions pour améliorer la connectivité globale du réseau. Par exemple, LinkedIn pourrait utiliser ces algorithmes pour suggérer des connexions professionnelles qui minimisent la distance entre les utilisateurs dans le réseau professionnel.

4. Planification Urbaine

Problème : Concevoir des systèmes de transport public ou des réseaux de distribution d'eau dans une ville.

• Application de Prim et Kruskal : Les urbanistes peuvent utiliser ces algorithmes pour planifier des systèmes de transport en commun, de distribution d'eau ou d'autres infrastructures de manière à minimiser les coûts de construction et de maintenance. Par exemple, lors de la construction d'un nouveau réseau de métro, ces algorithmes peuvent aider à déterminer les connexions entre les stations de manière à minimiser le coût total des rails posés.

5. Cartographie et Systèmes d'Information Géographique (SIG)

Problème : Construire des cartes de routes ou de sentiers optimales dans des parcs nationaux ou des zones urbaines.

• Application de Prim et Kruskal : Les géographes et les planificateurs peuvent utiliser ces algorithmes pour créer des cartes de routes ou de sentiers qui minimisent la distance totale ou le coût de construction. Par exemple, pour établir des sentiers de randonnée dans un parc national, ces algorithmes peuvent aider à choisir les routes qui offrent la meilleure couverture avec le minimum de construction nécessaire.

Ces algorithmes jouent un rôle crucial dans l'optimisation de divers systèmes, aidant à réduire les coûts et à améliorer l'efficacité dans des contextes variés allant des réseaux de communication aux systèmes de transport en passant par la planification urbaine et l'analyse des réseaux sociaux.

Conclusion

Les algorithmes de Prim et Kruskal sont deux méthodes efficaces pour trouver un arbre de recouvrement minimal dans un graphe pondéré. L'algorithme de Prim est basé sur l'ajout progressif de sommets, tandis que l'algorithme de Kruskal est basé sur l'ajout progressif d'arêtes. Les deux algorithmes utilisent des structures de données et des concepts spécifiques pour garantir l'efficacité et la correction de leur exécution.