Introduction

Bon retour dans la série sur les Algorithmes de Graphes ! Un Arbre Couvrant de Poids Minimum (MST) connecte chaque sommet d'un graphe pondéré en utilisant le poids total d'arêtes le moins cher possible, sans aucun cycle.

L'Algorithme de Kruskal construit le MST de manière gloutonne : il trie les arêtes de la moins chère à la plus chère et ajoute chacune d'elles, tant qu'elle ne crée pas de cycle. L'astuce pour détecter les cycles rapidement est une structure de données appelée union-find (également connue sous le nom d'ensemble disjoint).

Le graphe est non orienté et pondéré, donné sous la forme de n (sommets 0 à n - 1) et edges, un tableau plat de triplets [u0, v0, w0, ...] pour une arête non orientée u - v de poids w.

C'est parti !