Dans cet article, nous discuterons de l'algorithme de prim. Parallèlement à l'algorithme, nous verrons également la complexité, le fonctionnement, l'exemple et la mise en œuvre de l'algorithme de prim.
Avant de commencer le sujet principal, nous devrions discuter des termes fondamentaux et importants tels que l'arbre couvrant et l'arbre couvrant minimum.
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 le sujet principal.
L'algorithme de Prim est un algorithme glouton utilisé pour trouver l'arbre couvrant minimum à partir d'un graphique. L'algorithme de Prim trouve le sous-ensemble d'arêtes qui inclut chaque sommet du graphique de telle sorte que la somme des poids des arêtes puisse être minimisée.
L'algorithme de Prim commence par le nœud unique et explore tous les nœuds adjacents avec toutes les arêtes de connexion à chaque étape. Les arêtes avec les poids minimaux ne provoquant aucun cycle dans le graphique ont été sélectionnées.
Comment fonctionne l'algorithme de prim ?
L'algorithme de Prim est un algorithme glouton qui part d'un sommet et continue d'ajouter les arêtes ayant le plus petit poids jusqu'à ce que l'objectif soit atteint. Les étapes pour implémenter l'algorithme de prim sont indiquées comme suit -
- Tout d’abord, nous devons initialiser un MST avec le sommet choisi aléatoirement.
- Maintenant, nous devons trouver toutes les arêtes qui relient l’arbre de l’étape ci-dessus aux nouveaux sommets. Parmi les arêtes trouvées, sélectionnez l'arête minimale et ajoutez-la à l'arborescence.
- Répétez l’étape 2 jusqu’à ce que l’arbre couvrant minimum soit formé.
Les applications de l'algorithme de prim sont -
- L'algorithme de Prim peut être utilisé dans la conception de réseaux.
- Il peut être utilisé pour réaliser des cycles de réseau.
- Il peut également être utilisé pour poser des câbles électriques.
Exemple d'algorithme de prim
Voyons maintenant le fonctionnement de l'algorithme de prim à l'aide d'un exemple. Il sera plus facile de comprendre l'algorithme de prim à l'aide d'un exemple.
Supposons qu'un graphique pondéré soit -
Étape 1 - Tout d’abord, nous devons choisir un sommet dans le graphique ci-dessus. Choisissons B.
instanciation de Java
Étape 2 - Maintenant, nous devons choisir et ajouter l'arête la plus courte du sommet B. Il y a deux arêtes du sommet B qui sont B à C avec un poids de 10 et une arête B à D avec un poids de 4. Parmi les arêtes, l'arête BD a le poids minimum. . Alors, ajoutez-le au MST.
Étape 3 - Maintenant encore, choisissez le bord avec le poids minimum parmi tous les autres bords. Dans ce cas, les arêtes DE et CD sont de telles arêtes. Ajoutez-les au MST et explorez les adjacents de C, c'est-à-dire E et A. Alors, sélectionnez le bord DE et ajoutez-le au MST.
Étape 4 - Maintenant, sélectionnez le CD Edge et ajoutez-le au MST.
Étape 5 - Maintenant, choisissez l’autorité de certification Edge. Ici, nous ne pouvons pas sélectionner l’arête CE car cela créerait un cycle sur le graphique. Alors, choisissez l’autorité de certification Edge et ajoutez-la au MST.
Ainsi, le graphique produit à l’étape 5 est l’arbre couvrant minimum du graphique donné. Le coût du MST est indiqué ci-dessous -
Coût du MST = 4 + 2 + 1 + 3 = 10 unités.
Algorithme
Step 1: Select a starting vertex Step 2: Repeat Steps 3 and 4 until there are fringe vertices Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weight Step 4: Add the selected edge and the vertex to the minimum spanning tree T [END OF LOOP] Step 5: EXIT
Complexité de l'algorithme de Prim
Voyons maintenant la complexité temporelle de l'algorithme de Prim. Le temps d'exécution de l'algorithme de prim dépend de l'utilisation de la structure des données pour le graphique et de l'ordre des arêtes. Le tableau ci-dessous montre quelques choix -
| Structure de données utilisée pour le poids de bord minimum | Complexité temporelle |
|---|---|
| Matrice de contiguïté, recherche linéaire | O(|V|2) |
| Liste de contiguïté et tas binaire | O(|E|log |V|) |
| Liste de contiguïté et tas de Fibonacci | O(|E|+ |V| log |V|) |
L'algorithme de Prim peut être simplement implémenté en utilisant la représentation graphique de la matrice de contiguïté ou de la liste de contiguïté, et pour ajouter l'arête avec le poids minimum, il faut rechercher linéairement un tableau de poids. Cela nécessite O(|V|2) temps d'exécution. Il peut être encore amélioré en utilisant l'implémentation du tas pour trouver les bords de poids minimum dans la boucle interne de l'algorithme.
La complexité temporelle de l'algorithme de prim est O(E logV) ou O(V logV), où E est le non. des bords, et V est le non. de sommets.
Implémentation de l'algorithme de Prim
Voyons maintenant l'implémentation de l'algorithme de prim.
Programme: Écrivez un programme pour implémenter l'algorithme de prim en langage C.
#include #include #define vertices 5 /*Define the number of vertices in the graph*/ /* create minimum_key() method for finding the vertex that has minimum key-value and that is not added in MST yet */ int minimum_key(int k[], int mst[]) { int minimum = INT_MAX, min,i; /*iterate over all vertices to find the vertex with minimum key-value*/ for (i = 0; i <vertices; 0 i++) if (mst[i]="=" && k[i] < minimum ) min="i;" return min; } * create prim() method for constructing and printing the mst. g[vertices][vertices] is an adjacency matrix that defines graph mst.* void prim(int g[vertices][vertices]) { array of size equal to total number vertices storing mst* int parent[vertices]; k[vertices] selecting edge having weight* k[vertices]; mst[vertices]; i, count,edge,v; *here 'v' vertex* (i="0;" i vertices; mst[i]="0;" k[0]="0;" *it select as first parent[0]="-1;" set value parent[] -1 make it root (count="0;" count vertices-1; count++) *select vertex key not added in mst yet from vertices* mst); mst[edge]="1;" (v="0;" v v++) (g[edge][v] mst[v]="=" g[edge][v] k[v]) parent[v]="edge," k[v]="g[edge][v];" *print constructed spanning tree* printf('
weight
'); printf(' %d
', parent[i], g[i][parent[i]]); main() 0, 3, 0}, {0, 10, 4, {3, 2, 6}, 1}, 6, 1, }; prim(g); 0; pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/41/prims-algorithm-7.webp" alt="Prim"> <p>So, that's all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>