Dans cet article, nous discuterons de l'algorithme de Kruskal. Ici, nous verrons également la complexité, le fonctionnement, l'exemple et la mise en œuvre de l'algorithme de Kruskal.
Mais avant de passer directement à l’algorithme, nous devons d’abord comprendre les termes de base tels que spanning tree et minimum spanning tree.
Spanning Tree - Un arbre couvrant est le sous-graphe d'un graphe connecté non orienté.
Arbre couvrant minimum - L'arbre couvrant minimum peut être défini comme l'arbre couvrant dans lequel la somme des poids de l'arête est minimale. Le poids de l'arbre couvrant est la somme des poids attribués aux bords de l'arbre couvrant.
Maintenant, commençons par le sujet principal.
L'algorithme de Kruskal est utilisé pour trouver l'arbre couvrant minimum pour un graphique pondéré connecté. L'objectif principal de l'algorithme est de trouver le sous-ensemble d'arêtes grâce auquel nous pouvons parcourir chaque sommet du graphe. Il suit l’approche gourmande qui trouve une solution optimale à chaque étape au lieu de se concentrer sur un optimal global.
Comment fonctionne l'algorithme de Kruskal ?
Dans l'algorithme de Kruskal, nous partons des arêtes ayant le poids le plus faible et continuons à ajouter les arêtes jusqu'à ce que l'objectif soit atteint. Les étapes pour implémenter l'algorithme de Kruskal sont répertoriées comme suit -
- Tout d’abord, triez tous les bords du poids faible au poids élevé.
- Maintenant, prenez le bord avec le poids le plus faible et ajoutez-le à l'arbre couvrant. Si le bord à ajouter crée un cycle, rejetez le bord.
- Continuez à ajouter les arêtes jusqu'à ce que nous atteignions tous les sommets et qu'un arbre couvrant minimum soit créé.
Les applications de l'algorithme de Kruskal sont -
- L'algorithme de Kruskal peut être utilisé pour disposer le câblage électrique entre les villes.
- Il peut être utilisé pour établir des connexions LAN.
Exemple de l'algorithme de Kruskal
Voyons maintenant le fonctionnement de l'algorithme de Kruskal à l'aide d'un exemple. Il sera plus facile de comprendre l'algorithme de Kruskal à l'aide d'un exemple.
Supposons qu'un graphique pondéré soit -
Le poids des arêtes du graphique ci-dessus est donné dans le tableau ci-dessous -
| Bord | UN B | CA | ANNONCE | MAIS | avant JC | CD | DE |
| Poids | 1 | 7 | dix | 5 | 3 | 4 | 2 |
Maintenant, triez les arêtes indiquées ci-dessus dans l’ordre croissant de leurs poids.
| Bord | UN B | DE | avant JC | CD | MAIS | CA | ANNONCE |
| Poids | 1 | 2 | 3 | 4 | 5 | 7 | dix |
Maintenant, commençons à construire l’arbre couvrant minimum.
tutoriel SS
Étape 1 - Tout d'abord, ajoutez le bord UN B avec du poids 1 au MST.
Étape 2 - Ajouter le bord DE avec du poids 2 au MST car il ne crée pas le cycle.
Étape 3 - Ajouter le bord avant JC avec du poids 3 au MST, car il ne crée aucun cycle ou boucle.
Étape 4 - Maintenant, choisis le bord CD avec du poids 4 au MST, car il ne forme pas le cycle.
Étape 5 - Après cela, choisissez le bord MAIS avec du poids 5. L'inclusion de cette arête créera le cycle, alors jetez-le.
Étape 6 - Choisissez le bord CA avec du poids 7. L'inclusion de cette arête créera le cycle, alors jetez-le.
Étape 7 - Choisissez le bord ANNONCE avec du poids dix. L'inclusion de cette arête créera également le cycle, alors supprimez-le.
Ainsi, l'arbre couvrant minimum final obtenu à partir du graphique pondéré donné en utilisant l'algorithme de Kruskal est -
Le coût du MST est = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.
Maintenant, le nombre d’arêtes dans l’arbre ci-dessus est égal au nombre de sommets moins 1. L’algorithme s’arrête donc ici.
Algorithme
Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END
Complexité de l'algorithme de Kruskal
Voyons maintenant la complexité temporelle de l'algorithme de Kruskal.
La complexité temporelle de l'algorithme de Kruskal est O(E logE) ou O(V logV), où E est le non. des bords, et V est le non. de sommets.
Implémentation de l'algorithme de Kruskal
Voyons maintenant l'implémentation de l'algorithme de Kruskal.
Programme: Écrivez un programme pour implémenter l'algorithme de Kruskal en C++.
#include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes >> edges; for(int i = 0;i <edges;++i) { cout<> x >> y >> weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout <<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>