algorithmL'algorithme de Kruskal


Remarques

L'algorithme de Kruskal est un algorithme glouton utilisé pour trouver l' arbre à recouvrement minimal (MST) d'un graphique. Un arbre couvrant minimal est un arbre qui connecte tous les sommets du graphique et a le poids de bord total minimal.

L'algorithme de Kruskal le fait en sélectionnant de manière répétée des arêtes de poids minimal (qui ne figurent pas déjà dans le fichier MST) et les ajoute au résultat final si les deux sommets connectés par cette arête ne sont pas encore connectés dans le fichier MST. Union - La structure de données de recherche peut être utilisée pour vérifier si deux sommets sont déjà connectés ou non dans le fichier MST. Quelques propriétés de MST sont les suivantes:

  1. Un MST d'un graphe avec n sommets aura exactement n-1 arêtes.
  2. Il existe un chemin unique de chaque sommet à chaque autre sommet.

L'algorithme de Kruskal Exemples Liés