Algorithme de Prim avec une implémentation Java

1. Introduction

Dans ce didacticiel, nous apprenons d'abord ce que sont les arbres couvrant minimum. Ensuite, nous utiliserons l'algorithme de Prim pour en trouver un.

2. Arbre couvrant minimum

Un arbre couvrant minimum (MST) est un graphe connexe pondéré, non orienté, dont le poids total des arêtes a été minimisé en supprimant les arêtes les plus lourdes . En d'autres termes, nous gardons tous les sommets du graphe intacts, mais nous pouvons supprimer certains arêtes de sorte que la somme de toutes les arêtes soit au minimum.

Nous commençons par un graphique pondéré car cela n'a aucun sens de minimiser le poids total des arêtes si ces arêtes n'ont aucun poids. Jetons un œil à un exemple de graphique:

Le graphique ci-dessus est un graphique connexe pondéré, non orienté. Voici un MST de ce graphique:

Un MST d'un graphique n'est cependant pas unique. Si un graphique a plus d'un MST, alors chaque MST a le même poids d'arête total.

3. Algorithme de Prim

L'algorithme de Prim prend un graphe connecté pondéré, non orienté en entrée et renvoie un MST de ce graphe en sortie .

Cela fonctionne de manière gourmande . Dans la première étape, il sélectionne un sommet arbitraire. Ensuite, chaque nouvelle étape ajoute le sommet le plus proche à l'arbre construit jusqu'à présent jusqu'à ce qu'il n'y ait plus de sommet déconnecté.

Lançons l'algorithme de Prim sur ce graphique étape par étape:

En supposant que le sommet arbitraire pour démarrer l'algorithme est B, nous avons trois choix A, C et E à faire. Les poids correspondants des arêtes sont 2, 2 et 5, donc le minimum est 2. Dans ce cas, nous avons deux arêtes pesant 2, nous pouvons donc choisir l'une ou l'autre (peu importe laquelle). Choisissons A:

Nous avons maintenant un arbre avec deux sommets A et B. Nous pouvons sélectionner l'une des arêtes de A ou B non encore ajoutées qui mènent à un sommet non ajouté. Donc, nous pouvons choisir AC, BC ou BE.

L'algorithme de Prim choisit le minimum, qui est 2, ou BC:

Nous avons maintenant un arbre avec trois sommets et trois arêtes possibles pour avancer: CD, CE ou BE. AC n'est pas inclus car il n'ajouterait pas de nouveau sommet à l'arbre. Le poids minimum parmi ces trois est de 1.

Cependant, il y a deux arêtes pesant toutes les deux 1. Par conséquent, l'algorithme de Prim en choisit un (encore une fois, peu importe lequel) dans cette étape:

Il ne reste qu'un seul sommet à joindre, nous pouvons donc choisir entre CE et BE. Le poids minimum qui peut y connecter notre arbre est de 1, et l'algorithme de Prim le choisira:

Comme tous les sommets du graphe d'entrée sont maintenant présents dans l'arbre de sortie, l'algorithme de Prim se termine. Par conséquent, cet arbre est un MST du graphe d'entrée.

4. Mise en œuvre

Les sommets et les arêtes font des graphiques, nous avons donc besoin d'une structure de données pour stocker ces éléments. Créons la classe Edge :

public class Edge { private int weight; private boolean isIncluded = false; }

Chaque Edge doit avoir un poids puisque l'algorithme de Prim fonctionne sur des graphiques pondérés. isIncluded indique si Edge est présent ou non dans l'arborescence couvrant minimum.

Maintenant, ajoutons la classe Vertex :

public class Vertex { private String label = null; private Map edges = new HashMap(); private boolean isVisited = false; }

Chaque sommet peut éventuellement avoir une étiquette . Nous utilisons la carte des arêtes pour stocker les connexions entre les sommets. Enfin, isVisited montre si le sommet a été visité par l'algorithme de Prim jusqu'à présent ou non.

Créons notre classe Prim où nous implémenterons la logique:

public class Prim { private List graph; }

Une liste de sommets suffit pour stocker l'ensemble du graphe car à l'intérieur de chaque sommet , nous avons une carte pour identifier toutes les connexions. À l'intérieur de Prim, nous créons une méthode run () :

public void run() { if (graph.size() > 0) { graph.get(0).setVisited(true); } while (isDisconnected()) { Edge nextMinimum = new Edge(Integer.MAX_VALUE); Vertex nextVertex = graph.get(0); for (Vertex vertex : graph) { if (vertex.isVisited()) { Pair candidate = vertex.nextMinimum(); if (candidate.getValue().getWeight() < nextMinimum.getWeight()) { nextMinimum = candidate.getValue(); nextVertex = candidate.getKey(); } } } nextMinimum.setIncluded(true); nextVertex.setVisited(true); } }

Nous commençons par définir le premier élément du graphique List comme visité. Le premier élément peut être l'un des sommets en fonction de l'ordre dans lequel ils ont été ajoutés à la liste en premier lieu. isDisconnected () retourne true s'il y a un sommet non visité jusqu'à présent:

private boolean isDisconnected() { for (Vertex vertex : graph) { if (!vertex.isVisited()) { return true; } } return false; }

Alors que l'arbre couvrant minimum estDisconnected () , nous bouclons sur les sommets déjà visités et trouvons l' arête avec le poids minimum comme candidat pour nextVertex:

public Pair nextMinimum() { Edge nextMinimum = new Edge(Integer.MAX_VALUE); Vertex nextVertex = this; Iterator
    
      it = edges.entrySet() .iterator(); while (it.hasNext()) { Map.Entry pair = it.next(); if (!pair.getKey().isVisited()) { if (!pair.getValue().isIncluded()) { if (pair.getValue().getWeight() < nextMinimum.getWeight()) { nextMinimum = pair.getValue(); nextVertex = pair.getKey(); } } } } return new Pair(nextVertex, nextMinimum); }
    

Nous trouvons le minimum de tous les candidats dans la boucle principale et le stockons dans nextVertex . Ensuite, nous définissons nextVertex comme visité. La boucle continue jusqu'à ce que tous les sommets soient visités.

À la fin, chaque Edge avec isIncluded égal à true est présent.

Notez que puisque nextMinimum () parcourt les arêtes, la complexité temporelle de cette implémentation est O (V2) . Si nous stockons les arêtes dans une file d'attente prioritaire (triée par poids) à la place, l'algorithme fonctionnera en O (E log V) .

5. Test

Bon, maintenant que nous avons du code, testons-le avec un exemple réel. Tout d'abord, nous construisons notre graphique:

public static List createGraph() { List graph = new ArrayList(); Vertex a = new Vertex("A"); ... Vertex e = new Vertex("E"); Edge ab = new Edge(2); a.addEdge(b, ab); b.addEdge(a, ab); ... Edge ce = new Edge(1); c.addEdge(e, ce); e.addEdge(c, ce); graph.add(a); ... graph.add(e); return graph; }

Le constructeur de la classe Prim la prend et la stocke dans la classe. Nous pouvons imprimer le graphe d'entrée avec la méthode originalGraphToString () :

Prim prim = new Prim(createGraph()); System.out.println(prim.originalGraphToString());

Notre exemple affichera:

A --- 2 --- B A --- 3 --- C B --- 5 --- E B --- 2 --- C C --- 1 --- E C --- 1 --- D

Maintenant, nous exécutons l'algorithme de Prim et imprimons le MST résultant avec la méthode minimumSpanningTreeToString () :

prim.run(); prim.resetPrintHistory(); System.out.println(prim.minimumSpanningTreeToString());

Enfin, nous imprimons notre MST:

A --- 2 --- B B --- 2 --- C C --- 1 --- E C --- 1 --- D

6. Conclusion

Dans cet article, nous avons appris comment l'algorithme de Prim trouve un arbre couvrant minimum d'un graphique. Le code est disponible à l'adresse over sur GitHub.