Algorithme Spanning Tree de Prim

L'algorithme de Prim pour trouver l'arbre couvrant le coût minimum (comme l'algorithme de Kruskal) utilise l'approche gloutonne. L'algorithme de Prim partage une similitude avec leshortest path first algorithmes.

L'algorithme de Prim, contrairement à l'algorithme de Kruskal, traite les nœuds comme un seul arbre et continue d'ajouter de nouveaux nœuds à l'arbre couvrant à partir du graphe donné.

Pour contraster avec l'algorithme de Kruskal et pour mieux comprendre l'algorithme de Prim, nous utiliserons le même exemple -

Étape 1 - Retirez 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 - Choisissez n'importe quel nœud arbitraire comme nœud racine

Dans ce cas, nous choisissons Snode en tant que nœud racine de l'arbre couvrant de Prim. Ce nœud est choisi arbitrairement, donc n'importe quel nœud peut être le nœud racine. On peut se demander pourquoi une vidéo peut être un nœud racine. La réponse est donc que dans l'arbre couvrant tous les nœuds d'un graphe sont inclus et, comme il est connecté, il doit y avoir au moins un bord, qui le joindra au reste de l'arbre.

Étape 3 - Vérifiez les bords sortants et sélectionnez celui qui coûte le moins cher

Après avoir choisi le nœud racine S, nous voyons que S, A et S, C sont deux arêtes de poids 7 et 8, respectivement. On choisit l'arête S, A car elle est inférieure à l'autre.

Maintenant, l'arbre S-7-A est traité comme un nœud et nous vérifions toutes les arêtes qui en sortent. Nous sélectionnons celui qui a le coût le plus bas et l'incluons dans l'arbre.

Après cette étape, l'arbre S-7-A-3-C est formé. Maintenant, nous allons le traiter à nouveau comme un nœud et vérifier à nouveau tous les bords. Cependant, nous ne choisirons que l'avantage le moins coûteux. Dans ce cas, C-3-D est le nouveau bord, qui est inférieur au coût des autres bords 8, 6, 4, etc.

Après avoir ajouté le nœud Dà l'arbre couvrant, nous avons maintenant deux arêtes qui en sortent ayant le même coût, à savoir D-2-T et D-2-B. Ainsi, nous pouvons ajouter l'un ou l'autre. Mais la prochaine étape donnera à nouveau le bord 2 comme le moindre coût. Par conséquent, nous montrons un arbre couvrant avec les deux bords inclus.

Nous pouvons constater que l'arbre couvrant la sortie du même graphe en utilisant deux algorithmes différents est le même.