Tout savoir sur l’algorithme de Kruskal

Dans le domaine de l’informatique et des mathématiques appliquées, les graphes jouent un rôle fondamental. Ils permettent de modéliser de nombreux problèmes réels, comme ceux en rapport avec les réseaux de transport, les circuits électroniques ou les réseaux de communication. L’une des problématiques les plus importantes concernant les graphes est la détermination de l’arbre couvrant minimal d’un graphe pondéré. C’est ici qu’intervient une méthode efficace et largement utilisée, l’algorithme de Kruskal.

Qu’est-ce que l’algorithme de Kruskal ?

L’algorithme de Kruskal est considéré comme un algorithme de référence pour trouver l’arbre couvrant minimal dans un graphe non orienté et pondéré. Un arbre couvrant minimal ou minimum spanning tree (MST) est un sous-ensemble des arêtes du graphe qui connecte tous les nœuds ensemble sans cycles et avec le coût total minimal possible.

L’algorithme a été nommé d’après Joseph Kruskal, mathématicien et statisticien américain l’ayant développé en 1956. Il s’est appuyé sur des travaux antérieurs de plusieurs chercheurs, dont Vojtěch Jarník et Robert Clay Prim. Ces derniers ont également proposé des approches pour résoudre le même problème, comme les algorithmes de Prim et Boruvka. L’algorithme de Kruskal est toutefois le plus populaire, de par sa simplicité et sa rapidité d’implémentation.

Fonctionnement de l’algorithme de Kruskal

L’algorithme de Kruskal fonctionne de manière itérative. Il construit progressivement un arbre couvrant minimal à partir d’un graphe pondéré non orienté en reposant sur deux concepts clés.

Le tri des arêtes par poids croissant

Avant d’exécuter l’algorithme, toutes les arêtes du graphe sont triées par ordre croissant de poids. De cette manière, les arêtes les moins coûteuses sont prises en compte en premier lors de la construction de l’arbre couvrant.

La structure de données Union-Find

L’algorithme utilise une structure de données appelée Union-Find. Celle-ci permet de gérer efficacement les ensembles de nœuds et les fusions de composantes connexes. Une telle structure permet de déterminer si deux nœuds appartiennent à la même composante connexe et de fusionner efficacement les ensembles de nœuds.

Les composants et conditions clés d’un graphe

Pour que l’algorithme s’applique correctement et produise un MST valide, le graphe nécessite des éléments clés et doit répondre à certaines conditions essentielles. 

Composants fondamentaux pour la construction de l’arbre couvrant minimal

Ces composants clés incluent les sommets, les arêtes, les poids, les sous-graphes ou encore les cycles.

Sommet ou nœud

Il s’agit des points ou des entités distinctes du graph. Chaque sommet représente un élément et est connecté aux autres par des arêtes. Dans le contexte de Kruskal, chaque sommet est le point de départ et d’arrivée des arêtes que l’algorithme examinera pour construire un MST.

Les arêtes

Chaque arête, ou edge, relie deux sommets et peut être caractérisée par un poids ou un coût. On représente généralement une arête par une paire de sommets et le poids qui y est associé. Par exemple, l’arête (u,v,w) se compose des sommets u et v, et son poids est w.

Le poids

Cette valeur numérique est associée à chaque arête. Elle représente souvent une distance, un coût, une capacité, ou une autre mesure. Avec Kruskal, les poids sont utilisés pour trier les arêtes par ordre croissant, de manière à sélectionner en premier les arêtes les moins coûteuses.

Les sous-graphes

Il s’agit des portions du graphe d’origine. Au début du processus, chaque sommet est considéré comme un sous-graphe distinct. Puis progressivement, les sous-graphes se combinent en ajoutant des arêtes. Gérer efficacement ces sous-graphes est une étape cruciale pour éviter la formation de cycles dans l’arbre couvrant.

Les cycles

Dans un graphe, un cycle est un chemin fermé dans lequel un sommet peut être répété contrairement à une arête. Le cycle se forme lorsqu’il est possible de commencer à un sommet, de suivre une séquence d’arêtes, puis de revenir au point de départ sans retracer aucune arête. Or un MST ne peut pas contenir de cycle.

Trois conditions essentielles à la construction d’un arbre couvrant minimal

Le Graphe doit être non orienté. Dans ce contexte, les arêtes du graphe n’ont pas de sens particulier, et la connexion entre deux nœuds est réciproque. Avec un graphe orienté, les arêtes ont des directions et l’algorithme ne peut pas être appliqué directement. Pour traiter ce type de structure, on doit appliquer des algorithmes spécifiques, comme celui de Prim.

Le Graphe doit être pondéré, c’est-à-dire qu’un poids doit être associé à chaque arête. Il représente le coût ou l’effort lié à son utilisation. Il peut s’agir d’une valeur numérique, d’une distance, d’un temps ou d’une autre mesure quantifiable en rapport avec la problématique. Kruskal utilise les poids des arêtes pour comparer et sélectionner les arêtes à ajouter au minimum spanning tree. Il va privilégier celles dont les poids sont les plus faibles, de manière à minimiser le poids total de l’arbre couvrant.

Enfin, le graphe doit être connexe. Cela signifie qu’il existe un chemin entre chaque paire de nœuds et ces derniers doivent être accessibles les uns aux autres via des arêtes. Un graphe déconnecté, c’est-à-dire contenant des groupes de nœuds isolés les uns des autres, empêche Kruskal de produire des arbres couvrants valides. 

Atteindre un minimum spanning tree valide grâce à un processus précis par étape

La première étape est celle de l’initialisation. Il faut créer un ensemble de sous-ensembles distincts, chacun contenant un seul sommet. Au départ, chaque sommet est son propre sous-ensemble. On peut réaliser cette opération à l’aide de la structure de données union-find. L’étape suivante consiste à trier toutes les arêtes, en fonction de leur poids, par ordre croissant. L’objectif est de toujours choisir la plus petite arête disponible. Une fois les arêtes triées, une procédure itérative se met en place.

Pour chaque arête, le programme vérifie si elle peut s’ajouter au MST sans former de cycle. L’utilisation de la structure union-find permet de vérifier si les deux sommets de l’arête appartiennent à deux sous-ensembles différents. Si c’est le cas, l’arête s’ajoute à l’arbre couvrant et les deux sous-ensembles fusionnent.

Dans le cas contraire, il est impératif d’ignorer l’arête pour éviter un cycle. Le processus se répète alors jusqu’à ce que l’arbre couvrant contienne n− 1 arêtes, dans lequel n correspond au nombre de sommets dans le graphe.

 

La méthode peut s’appliquer de la manière suivante en code Java :

import java.util.ArrayList; 

import java.util.Comparator; 

import java.util.List; 

 

public class KruskalsMST { 

 

static class Edge { 

int src, dest, weight; 

 

public Edge(int src, int dest, int weight) 

{ 

this.src = src; 

this.dest = dest; 

this.weight = weight; 

} 

} 

 

static class Subset { 

int parent, rank; 

 

public Subset(int parent, int rank) 

{ 

this.parent = parent; 

this.rank = rank; 

} 

} 

 

public static void main(String[] args) 

{ 

int V = 4; 

List graphEdges = new ArrayList( 

List.of(new Edge(0, 1, 10), new Edge(0, 2, 6), 

new Edge(0, 3, 5), new Edge(1, 3, 15), 

new Edge(2, 3, 4))); 

 

graphEdges.sort(new Comparator() { 

@Override public int compare(Edge o1, Edge o2) 

{ 

return o1.weight – o2.weight; 

} 

}); 

 

kruskals(V, graphEdges); 

} 

 

private static void kruskals(int V, List edges) 

{ 

int j = 0; 

int noOfEdges = 0; 

 

Subset subsets[] = new Subset[V]; 

 

Edge results[] = new Edge[V]; 

 

for (int i = 0; i < V; i++) { 

subsets[i] = new Subset(i, 0); 

} 

 

while (noOfEdges < V – 1) { 

 

Edge nextEdge = edges.get(j); 

int x = findRoot(subsets, nextEdge.src); 

int y = findRoot(subsets, nextEdge.dest); 

 

if (x != y) { 

results[noOfEdges] = nextEdge; 

union(subsets, x, y); 

noOfEdges++; 

} 

 

j++; 

} 

 

System.out.println( 

« Following are the edges of the constructed MST: »); 

int minCost = 0; 

for (int i = 0; i < noOfEdges; i++) { 

System.out.println(results[i].src +  » — « 

+ results[i].dest +  » == « 

+ results[i].weight); 

minCost += results[i].weight; 

} 

System.out.println(« Total cost of MST:  » + minCost); 

} 

 

private static void union(Subset[] subsets, int x, 

int y) 

{ 

int rootX = findRoot(subsets, x); 

int rootY = findRoot(subsets, y); 

 

if (subsets[rootY].rank < subsets[rootX].rank) { 

subsets[rootY].parent = rootX; 

} 

else if (subsets[rootX].rank 

< subsets[rootY].rank) { 

subsets[rootX].parent = rootY; 

} 

else { 

subsets[rootY].parent = rootX; 

subsets[rootX].rank++; 

} 

} 

 

private static int findRoot(Subset[] subsets, int i) 

{ 

if (subsets[i].parent == i) 

return subsets[i].parent; 

 

subsets[i].parent 

= findRoot(subsets, subsets[i].parent); 

return subsets[i].parent; 

} 

}

 

Un traitement spécifique des arêtes et des nœuds

Kruskal traite les arêtes et les nœuds de façon très méthodique. Comme nous l’avons vu précédemment, les edges sont triés en fonction de leur poids. De cette manière, la plus petite disponible est toujours la première choisie, évitant ainsi la formation de cycles. Les nœuds quant à eux sont gérés par un ensemble de sous-ensembles. Cette méthode permet de suivre les connexions sans cycles. 

Complexité temporelle de l’algorithme de Kruskal

L’algorithme présente une complexité temporelle de O(E log E + V log V), dans laquelle E correspond au nombre d’arêtes et V au nombre de nœuds dans le graph. Elle se décompose de la manière suivante :

• le tri des arêtes par ordre croissant présente une complexité de O(E log E) ;
• les opérations de fusion de composantes connexes comme Union-Find ont une complexité de O(E α[V]), α étant la fonction d’Ackermann ;
• l’itération sur les arêtes a une complexité de O(E).

 

Dans quels cas Kruskal est-il préféré à d’autres algorithmes de graphe ?

Particulièrement efficace pour les graphes clairsemés, Kruskal surpasse souvent d’autres algorithmes comme celui de Prim dans ce type de contexte. D’autant que son efficacité augmente encore si les arêtes sont triées ou peuvent l’être rapidement. Cette méthode s’adapte également aux applications distribuées. Elle permet de traiter les arêtes de manière indépendante, facilitant ainsi son implémentation.

Une méthode qui présente des avantages

Kruskal se distingue par sa simplicité, son efficacité et sa flexibilité. La méthode est plutôt facile à comprendre et à implémenter. Souvent plus rapide que les autres algorithmes de l’arbre couvrant minimal, il est adaptable à diverses structures. Il peut en outre être optimisé grâce à l’utilisation de structures de données efficaces comme les ensembles disjoints. Il garantit des performances solides dans différents scénarios.

Quiconque s’intéressant aux algorithmes de graphes et aux structures de données à tout intérêt à ajouter Kruskal à son arsenal de compétences. Une telle méthode présente un impact majeur et durable sur de nombreux domaines scientifiques et d’ingénierie.