Motivation

Kruskal maintient la forêt croissante d'arêtes choisies dans une structure union-find. Pour ajouter une arête en toute sécurité, il vérifie si les deux extrémités sont déjà dans le même ensemble (ce qui créerait un cycle).

Pourquoi apprendre Kruskal ?

• MST réels : conception de réseaux, partitionnement de données (clustering) et pose de câbles ou de routes à un coût minimal.
• Union-find : une structure magnifique et réutilisable pour suivre la connectivité qui apparaît partout en informatique.
• Correction gloutonne : un autre exemple où le fait de toujours choisir l'option sûre la moins chère produit l'optimum global.

Tous les arbres couvrants minimaux d'un graphe utilisent le même multiensemble de poids d'arêtes, de sorte que le poids total (et l'arête la plus grande) est unique.