Algorithme de Kruskal pour couvrir les arbres avec une implémentation Java

1. Vue d'ensemble

Dans un article précédent, nous avons présenté l'algorithme de Prim pour trouver les arbres couvrant minimum. Dans cet article, nous utiliserons une autre approche, l'algorithme de Kruskal, pour résoudre les problèmes de spanning tree minimum et maximum.

2. Spanning Tree

Un arbre couvrant d'un graphe non orienté est un sous-graphe connecté qui couvre tous les nœuds du graphe avec le nombre minimum d'arêtes possible. En général, un graphe peut avoir plus d'un arbre couvrant. La figure suivante montre un graphique avec un arbre couvrant (les bords de l'arbre couvrant sont en rouge):

Si le graphique est pondéré par les bords, nous pouvons définir le poids d'un arbre couvrant comme la somme des poids de tous ses bords. Un arbre couvrant minimum est un arbre couvrant dont le poids est le plus petit parmi tous les arbres couvrant possibles. La figure suivante montre un arbre couvrant minimum sur un graphique pondéré par les bords:

De même, un arbre couvrant maximum a le poids le plus élevé parmi tous les arbres couvrant. La figure suivante montre un arbre couvrant maximum sur un graphique pondéré par les bords:

3. Algorithme de Kruskal

Étant donné un graphique, nous pouvons utiliser l'algorithme de Kruskal pour trouver son arbre couvrant minimum. Si le nombre de nœuds dans un graphe est V , alors chacun de ses arbres couvrant doit avoir des arêtes (V-1) et ne contenir aucun cycle. Nous pouvons décrire l'algorithme de Kruskal dans le pseudo-code suivant:

Initialize an empty edge set T. Sort all graph edges by the ascending order of their weight values. foreach edge in the sorted edge list Check whether it will create a cycle with the edges inside T. If the edge doesn't introduce any cycles, add it into T. If T has (V-1) edges, exit the loop. return T

Exécutons l'algorithme de Kruskal pour un arbre couvrant minimum sur notre exemple de graphique étape par étape:

Tout d'abord, on choisit l'arête (0, 2) car elle a le plus petit poids. Ensuite, nous pouvons ajouter des arêtes (3, 4) et (0, 1) car elles ne créent aucun cycle. Maintenant, le prochain candidat est l'arête (1, 2) de poids 9. Cependant, si nous incluons cette arête, nous produirons un cycle (0, 1, 2). Par conséquent, nous rejetons ce bord et continuons à choisir le plus petit suivant. Enfin, l'algorithme termine en ajoutant l'arête (2, 4) de poids 10.

Pour calculer l'arbre couvrant maximum, nous pouvons changer l'ordre de tri en ordre décroissant. Les autres étapes restent les mêmes. La figure suivante montre la construction étape par étape d'un arbre couvrant maximum sur notre exemple de graphique.

4. Détection de cycle avec un ensemble disjoint

Dans l'algorithme de Kruskal, la partie cruciale est de vérifier si une arête créera un cycle si nous l'ajoutons à l'ensemble d'arêtes existant. Il existe plusieurs algorithmes de détection de cycle de graphes que nous pouvons utiliser. Par exemple, nous pouvons utiliser un algorithme de recherche en profondeur d'abord (DFS) pour parcourir le graphique et détecter s'il y a un cycle.

Cependant, nous devons faire une détection de cycle sur les arêtes existantes à chaque fois que nous testons une nouvelle arête. Une solution plus rapide consiste à utiliser l'algorithme Union-Find avec la structure de données disjointe, car il utilise également une approche d'ajout de bord incrémentiel pour détecter les cycles. Nous pouvons intégrer cela dans notre processus de construction de Spanning Tree.

4.1. Construction d'un ensemble disjoint et d'un arbre couvrant

Tout d'abord, nous traitons chaque nœud du graphe comme un ensemble individuel ne contenant qu'un seul nœud. Ensuite, chaque fois que nous introduisons une arête, nous vérifions si ses deux nœuds sont dans le même ensemble. Si la réponse est oui, cela créera un cycle. Sinon, nous fusionnons les deux ensembles disjoints en un seul ensemble et incluons l'arête de l'arbre couvrant.

Nous pouvons répéter les étapes ci-dessus jusqu'à ce que nous construisions tout l'arbre couvrant.

Par exemple, dans la construction d'arbre couvrant minimum ci-dessus, nous avons d'abord 5 ensembles de nœuds: {0}, {1}, {2}, {3}, {4}. Lorsque nous vérifions la première arête (0, 2), ses deux nœuds sont dans des ensembles de nœuds différents. Par conséquent, nous pouvons inclure ce bord et fusionner {0} et {2} en un seul ensemble {0, 2}.

Nous pouvons faire des opérations similaires pour les arêtes (3, 4) et (0, 1). Les ensembles de nœuds deviennent alors {0, 1, 2} et {3, 4}. Lorsque nous vérifions l'arête suivante (1, 2), nous pouvons voir que les deux nœuds de cette arête sont dans le même ensemble. Par conséquent, nous rejetons ce bord et continuons à vérifier le suivant. Enfin, l'arête (2, 4) satisfait notre condition, et nous pouvons l'inclure pour l'arbre couvrant minimum.

4.2. Implémentation d'ensemble disjoint

Nous pouvons utiliser une structure arborescente pour représenter un ensemble disjoint. Chaque nœud a un pointeur parent pour référencer son nœud parent. Dans chaque ensemble, il existe un nœud racine unique qui représente cet ensemble. Le nœud racine a un pointeur parent auto-référencé .

Utilisons une classe Java pour définir les informations de l'ensemble disjoint:

public class DisjointSetInfo { private Integer parentNode; DisjointSetInfo(Integer parent) { setParentNode(parent); } //standard setters and getters }

Étiquetons chaque nœud de graphe avec un nombre entier, à partir de 0. Nous pouvons utiliser une structure de données de liste, Nœuds de liste , pour stocker les informations d'ensemble disjoint d'un graphe. Au début, chaque nœud est le membre représentatif de son propre ensemble:

void initDisjointSets(int totalNodes) { nodes = new ArrayList(totalNodes); for (int i = 0; i < totalNodes; i++) { nodes.add(new DisjointSetInfo(i)); } } 

4.3. Rechercher une opération

Pour trouver l'ensemble auquel appartient un nœud, nous pouvons suivre la chaîne parent du nœud vers le haut jusqu'à ce que nous atteignions le nœud racine:

Integer find(Integer node) { Integer parent = nodes.get(node).getParentNode(); if (parent.equals(node)) { return node; } else { return find(parent); } }

Il est possible d'avoir une structure arborescente très déséquilibrée pour un ensemble disjoint. Nous pouvons améliorer l' opération de recherche en utilisant la technique de compression p ath .

Étant donné que chaque nœud que nous visitons sur le chemin du nœud racine fait partie du même ensemble, nous pouvons attacher le nœud racine directement à sa référence parent . La prochaine fois que nous visitons ce nœud, nous avons besoin d'un chemin de recherche pour obtenir le nœud racine:

Integer pathCompressionFind(Integer node) { DisjointSetInfo setInfo = nodes.get(node); Integer parent = setInfo.getParentNode(); if (parent.equals(node)) { return node; } else { Integer parentNode = find(parent); setInfo.setParentNode(parentNode); return parentNode; } }

4.4. Opération syndicale

Si les deux nœuds d'une arête sont dans des ensembles différents, nous combinerons ces deux ensembles en un seul. Nous pouvons réaliser cette opération d' union en définissant la racine d'un nœud représentatif sur l'autre nœud représentatif:

void union(Integer rootU, Integer rootV) { DisjointSetInfo setInfoU = nodes.get(rootU); setInfoU.setParentNode(rootV); }

Cette simple opération d'union pourrait produire un arbre très déséquilibré car nous avons choisi un nœud racine aléatoire pour l'ensemble fusionné. Nous pouvons améliorer les performances en utilisant une technique d' union par rang .

Since it is tree depth that affects the running time of the find operation, we attach the set with the shorter tree to the set with the longer tree. This technique only increases the depth of the merged tree if the original two trees have the same depth.

To achieve this, we first add a rank property to the DisjointSetInfo class:

public class DisjointSetInfo { private Integer parentNode; private int rank; DisjointSetInfo(Integer parent) { setParentNode(parent); setRank(0); } //standard setters and getters }

In the beginning, a single node disjoint has a rank of 0. During the union of two sets, the root node with a higher rank becomes the root node of the merged set. We increase the new root node's rank by one only if the original two ranks are the same:

void unionByRank(int rootU, int rootV) { DisjointSetInfo setInfoU = nodes.get(rootU); DisjointSetInfo setInfoV = nodes.get(rootV); int rankU = setInfoU.getRank(); int rankV = setInfoV.getRank(); if (rankU < rankV) { setInfoU.setParentNode(rootV); } else { setInfoV.setParentNode(rootU); if (rankU == rankV) { setInfoU.setRank(rankU + 1); } } }

4.5. Cycle Detection

We can determine whether two nodes are in the same disjoint set by comparing the results of two find operations. If they have the same representive root node, then we've detected a cycle. Otherwise, we merge the two disjoint sets by using a union operation:

boolean detectCycle(Integer u, Integer v) { Integer rootU = pathCompressionFind(u); Integer rootV = pathCompressionFind(v); if (rootU.equals(rootV)) { return true; } unionByRank(rootU, rootV); return false; } 

The cycle detection, with the union by rank technique alone, has a running time of O(logV). We can achieve better performance with both path compression and union by rank techniques. The running time is O(α(V)), where α(V) is the inverse Ackermann function of the total number of nodes. It is a small constant that is less than 5 in our real-world computations.

5. Java Implementation of Kruskal’s Algorithm

We can use the ValueGraph data structure in Google Guava to represent an edge-weighted graph.

To use ValueGraph, we first need to add the Guava dependency to our project's pom.xml file:

     com.google.guava     guava     28.1-jre 

We can wrap the above cycle detection methods into a CycleDetector class and use it in Kruskal's algorithm. Since the minimum and maximum spanning tree construction algorithms only have a slight difference, we can use one general function to achieve both constructions:

ValueGraph spanningTree(ValueGraph graph, boolean minSpanningTree) { Set edges = graph.edges(); List edgeList = new ArrayList(edges); if (minSpanningTree) { edgeList.sort(Comparator.comparing(e -> graph.edgeValue(e).get())); } else { edgeList.sort(Collections.reverseOrder(Comparator.comparing(e -> graph.edgeValue(e).get()))); } int totalNodes = graph.nodes().size(); CycleDetector cycleDetector = new CycleDetector(totalNodes); int edgeCount = 0; MutableValueGraph spanningTree = ValueGraphBuilder.undirected().build(); for (EndpointPair edge : edgeList) { if (cycleDetector.detectCycle(edge.nodeU(), edge.nodeV())) { continue; } spanningTree.putEdgeValue(edge.nodeU(), edge.nodeV(), graph.edgeValue(edge).get()); edgeCount++; if (edgeCount == totalNodes - 1) { break; } } return spanningTree; }

In Kruskal's algorithm, we first sort all graph edges by their weights. This operation takes O(ElogE) time, where E is the total number of edges.

Ensuite, nous utilisons une boucle pour parcourir la liste des bords triés. À chaque itération, nous vérifions si un cycle sera formé en ajoutant l'arête dans l'ensemble d'arêtes courant de Spanning Tree. Cette boucle avec la détection de cycle prend au plus le temps O (ElogV) .

Par conséquent, le temps de fonctionnement global est O (ELogE + ELogV) . Puisque la valeur de E est dans l'échelle de O (V2) , la complexité temporelle de l'algorithme de Kruskal est O (ElogE) ou O (ElogV) .

6. Conclusion

Dans cet article, nous avons appris à utiliser l'algorithme de Kruskal pour trouver un arbre couvrant minimum ou maximum d'un graphique. Comme toujours, le code source de l'article est disponible à l'adresse over sur GitHub.