Algorithme Spanning Tree de Kruskal

L'algorithme de Kruskal pour trouver l'arbre couvrant le coût minimum utilise l'approche gloutonne. Cet algorithme traite le graphique comme une forêt et chaque nœud qu'il possède comme un arbre individuel. Une arborescence se connecte à une autre uniquement et uniquement si elle a le moindre coût parmi toutes les options disponibles et ne viole pas les propriétés MST.

Pour comprendre l'algorithme de Kruskal, considérons l'exemple suivant -

Étape 1 - Supprimez toutes les boucles et les bords parallèles

Supprimez toutes les boucles et les arêtes parallèles du graphique donné.

En cas d'arêtes parallèles, conserver celle qui a le moins de coût associé et supprimer tous les autres.

Étape 2 - Disposez tous les bords dans leur ordre croissant de poids

L'étape suivante consiste à créer un ensemble d'arêtes et de poids, et de les organiser dans un ordre croissant de pondération (coût).

Étape 3 - Ajouter l'arête qui a le moins de poids

Nous commençons maintenant à ajouter des arêtes au graphique en commençant par celle qui a le moins de poids. Tout au long, nous continuerons à vérifier que les propriétés de recouvrement restent intactes. Dans le cas où, en ajoutant une arête, la propriété spanning tree ne tient pas, nous envisagerons de ne pas inclure l'arête dans le graphe.

Le moindre coût est de 2 et les arêtes impliquées sont B, D et D, T. Nous les ajoutons. Leur ajout ne viole pas les propriétés de Spanning Tree, nous continuons donc à notre sélection d'arêtes suivante.

Le coût suivant est de 3 et les arêtes associées sont A, C et C, D. Nous les ajoutons à nouveau -

Le coût suivant dans le tableau est 4, et nous observons que l'ajouter créera un circuit dans le graphique. -

Nous l'ignorons. Dans le processus, nous ignorerons / éviterons tous les bords qui créent un circuit.

On observe que les arêtes de coût 5 et 6 créent également des circuits. Nous les ignorons et passons à autre chose.

Il ne nous reste plus qu'un seul nœud à ajouter. Entre les deux arêtes les moins coûteuses disponibles 7 et 8, nous ajouterons l'arête de coût 7.

En ajoutant l'arête S, A, nous avons inclus tous les nœuds du graphe et nous avons maintenant un arbre couvrant le coût minimum.