Introduction à l'algorithme de Prim :
Nous avons discuté Algorithme de Kruskal pour l'arbre couvrant minimum . Comme l’algorithme de Kruskal, l’algorithme de Prim est également un Algorithme gourmand . Cet algorithme commence toujours par un seul nœud et passe par plusieurs nœuds adjacents, afin d'explorer tous les bords connectés en cours de route.
L’algorithme commence avec un arbre couvrant vide. L'idée est de conserver deux ensembles de sommets. Le premier ensemble contient les sommets déjà inclus dans le MST, et l'autre ensemble contient les sommets non encore inclus. À chaque étape, il prend en compte toutes les arêtes qui relient les deux ensembles et sélectionne l’arête de poids minimum parmi ces arêtes. Après avoir sélectionné le bord, il déplace l’autre extrémité du bord vers l’ensemble contenant MST.
Un groupe d’arêtes qui relie deux ensembles de sommets dans un graphe est appelé coupe en théorie des graphes . Ainsi, à chaque étape de l'algorithme de Prim, trouvez une coupe, choisissez l'arête de poids minimum de la coupe et incluez ce sommet dans l'ensemble MST (l'ensemble qui contient les sommets déjà inclus).
Comment fonctionne l’algorithme de Prim ?
Le fonctionnement de l’algorithme de Prim peut être décrit en utilisant les étapes suivantes :
Étape 1: Déterminez un sommet arbitraire comme sommet de départ du MST.
Étape 2: Suivez les étapes 3 à 5 jusqu'à ce qu'il y ait des sommets qui ne sont pas inclus dans le MST (appelés sommet de frange).
Étape 3: Trouvez les arêtes reliant n’importe quel sommet d’arbre aux sommets des franges.
Étape 4: Trouvez le minimum parmi ces arêtes.
Étape 5 : Ajoutez l'arête choisie au MST si elle ne forme aucun cycle.
Étape 6 : Renvoyez le MST et quittez
Note: Pour déterminer un cycle, nous pouvons diviser les sommets en deux ensembles [un ensemble contient les sommets inclus dans MST et l'autre contient les sommets des franges.]
Pratique recommandée Arbre couvrant minimum Essayez-le !Illustration de l'algorithme de Prim :
Considérons le graphique suivant comme exemple pour lequel nous devons trouver le minimum Spanning Tree (MST).
Exemple de graphique
Étape 1: Tout d’abord, nous sélectionnons un sommet arbitraire qui fait office de sommet de départ du Minimum Spanning Tree. Ici, nous avons sélectionné le sommet 0 comme sommet de départ.
0 est sélectionné comme sommet de départ
Étape 2: Toutes les arêtes reliant le MST incomplet et les autres sommets sont les arêtes {0, 1} et {0, 7}. Entre ces deux, l’arête de poids minimum est {0, 1}. Incluez donc l'arête et le sommet 1 dans le MST.
1 est ajouté au MST
np.zérosÉtape 3: Les arêtes reliant le MST incomplet aux autres sommets sont {0, 7}, {1, 7} et {1, 2}. Parmi ces arêtes, le poids minimum est de 8, qui correspond aux arêtes {0, 7} et {1, 2}. Incluons ici l'arête {0, 7} et le sommet 7 dans le MST. [Nous aurions également pu inclure l'arête {1, 2} et le sommet 2 dans le MST].
7 est ajouté dans le MST
Étape 4: Les arêtes qui relient le MST incomplet aux sommets des franges sont {1, 2}, {7, 6} et {7, 8}. Ajoutez l'arête {7, 6} et le sommet 6 dans le MST car il a le moins de poids (c'est-à-dire 1).
6 est ajouté dans le MST
Étape 5 : Les arêtes de connexion sont désormais {7, 8}, {1, 2}, {6, 8} et {6, 5}. Incluez l'arête {6, 5} et le sommet 5 dans le MST car l'arête a le poids minimum (c'est-à-dire 2) parmi eux.
Inclure le sommet 5 dans le MST
Étape 6 : Parmi les arêtes de connexion actuelles, l'arête {5, 2} a le poids minimum. Incluez donc cette arête et le sommet 2 dans le MST.
Inclure le sommet 2 dans le MST
Étape 7 : Les arêtes de connexion entre le MST incomplet et les autres arêtes sont {2, 8}, {2, 3}, {5, 3} et {5, 4}. L'arête avec un poids minimum est l'arête {2, 8} qui a un poids de 2. Incluez donc cette arête et le sommet 8 dans le MST.
Ajouter le sommet 8 dans le MST
Étape 8 : Voyez ici que les arêtes {7, 8} et {2, 3} ont toutes deux le même poids qui est minimum. Mais 7 fait déjà partie de MST. Nous allons donc considérer l'arête {2, 3} et inclure cette arête et son sommet 3 dans le MST.
Inclure le sommet 3 dans MST
Étape 9 : Seul le sommet 4 reste à inclure. Le bord pondéré minimum du MST incomplet à 4 est {3, 4}.
Inclure le sommet 4 dans le MST
La structure finale du MST est la suivante et le poids des arêtes du MST est (4 + 8 + 1 + 2 + 4 + 2 + 7 + 9) = 37 .
La structure du MST formée à l'aide de la méthode ci-dessus
Note: Si nous avions sélectionné l'arête {1, 2} à la troisième étape, le MST ressemblerait à ce qui suit.
Structure du MST alternatif si nous avions sélectionné le bord {1, 2} dans le MST
Comment implémenter l’algorithme de Prim ?
Suivez les étapes indiquées pour utiliser le L'algorithme de Prim mentionné ci-dessus pour trouver le MST d'un graphique :
- Créer un ensemble mstSet qui garde la trace des sommets déjà inclus dans MST.
- Attribuez une valeur clé à tous les sommets du graphique d’entrée. Initialisez toutes les valeurs clés comme INFINITE. Attribuez la valeur clé à 0 pour le premier sommet afin qu'il soit sélectionné en premier.
- Alors que mstSet n'inclut pas tous les sommets
- Choisissez un sommet dans ce n'est pas là dans mstSet et a une valeur de clé minimale.
- Inclure dans dans le mstSet .
- Mettre à jour la valeur clé de tous les sommets adjacents de dans . Pour mettre à jour les valeurs clés, parcourez tous les sommets adjacents.
- Pour chaque sommet adjacent dans , si le poids du bord u-v est inférieur à la valeur clé précédente de dans , mettez à jour la valeur clé en tant que poids de u-v .
L'idée d'utiliser des valeurs clés est de choisir le bord de poids minimum à partir du couper . Les valeurs clés sont utilisées uniquement pour les sommets qui ne sont pas encore inclus dans MST, la valeur clé pour ces sommets indique les arêtes de poids minimum les reliant à l'ensemble des sommets inclus dans MST.
Ci-dessous la mise en œuvre de l’approche :
C++
// A C++ program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> using> namespace> std;> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] void printMST(int parent[], int graph[V][V]) { cout << 'Edge Weight
'; for (int i = 1; i cout << parent[i] << ' - ' << i << ' ' << graph[i][parent[i]] << '
'; } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // Print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; } // This code is contributed by rathbhupendra> |
>
>
C
// A C program for Prim's Minimum> // Spanning Tree (MST) algorithm. The program is> // for adjacency matrix representation of the graph> #include> #include> #include> // Number of vertices in the graph> #define V 5> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> int> minKey(>int> key[],>bool> mstSet[])> {> >// Initialize min value> >int> min = INT_MAX, min_index;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] int printMST(int parent[], int graph[V][V]) { printf('Edge Weight
'); for (int i = 1; i printf('%d - %d %d
', parent[i], i, graph[i][parent[i]]); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation void primMST(int graph[V][V]) { // Array to store constructed MST int parent[V]; // Key values used to pick minimum weight edge in cut int key[V]; // To represent set of vertices included in MST bool mstSet[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = INT_MAX, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first // vertex. key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex from the // set of vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for vertices // not yet included in MST Update the key only // if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver's code int main() { int graph[V][V] = { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); return 0; }> |
>
>
Java
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency matrix> // representation of the graph> import> java.io.*;> import> java.lang.*;> import> java.util.*;> class> MST {> >// Number of vertices in the graph> >private> static> final> int> V =>5>;> >// A utility function to find the vertex with minimum> >// key value, from the set of vertices not yet included> >// in MST> >int> minKey(>int> key[], Boolean mstSet[])> >{> >// Initialize min value> >int> min = Integer.MAX_VALUE, min_index = ->1>;> >for> (>int> v =>0>; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print the constructed MST // stored in parent[] void printMST(int parent[], int graph[][]) { System.out.println('Edge Weight'); for (int i = 1; i System.out.println(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]]); } // Function to construct and print MST for a graph // represented using adjacency matrix representation void primMST(int graph[][]) { // Array to store constructed MST int parent[] = new int[V]; // Key values used to pick minimum weight edge in // cut int key[] = new int[V]; // To represent set of vertices included in MST Boolean mstSet[] = new Boolean[V]; // Initialize all keys as INFINITE for (int i = 0; i key[i] = Integer.MAX_VALUE; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex key[0] = 0; // First node is always root of MST parent[0] = -1; // The MST will have V vertices for (int count = 0; count 1; count++) { // Pick the minimum key vertex from the set of // vertices not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of the // adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (int v = 0; v // graph[u][v] is non zero only for adjacent // vertices of m mstSet[v] is false for // vertices not yet included in MST Update // the key only if graph[u][v] is smaller // than key[v] if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] parent[v] = u; key[v] = graph[u][v]; } } // Print the constructed MST printMST(parent, graph); } public static void main(String[] args) { MST t = new MST(); int graph[][] = new int[][] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution t.primMST(graph); } } // This code is contributed by Aakash Hasija> |
>
>
Terminal Linux Kali
Python3
# A Python3 program for> # Prim's Minimum Spanning Tree (MST) algorithm.> # The program is for adjacency matrix> # representation of the graph> # Library for INT_MAX> import> sys> class> Graph():> >def> __init__(>self>, vertices):> >self>.V>=> vertices> >self>.graph>=> [[>0> for> column>in> range>(vertices)]> >for> row>in> range>(vertices)]> ># A utility function to print> ># the constructed MST stored in parent[]> >def> printMST(>self>, parent):> >print>(>'Edge Weight'>)> >for> i>in> range>(>1>,>self>.V):> >print>(parent[i],>'-'>, i,>' '>,>self>.graph[i][parent[i]])> ># A utility function to find the vertex with> ># minimum distance value, from the set of vertices> ># not yet included in shortest path tree> >def> minKey(>self>, key, mstSet):> ># Initialize min value> >min> => sys.maxsize> >for> v>in> range>(>self>.V):> >if> key[v] <>min> and> mstSet[v]>=>=> False>:> >min> => key[v]> >min_index>=> v> >return> min_index> ># Function to construct and print MST for a graph> ># represented using adjacency matrix representation> >def> primMST(>self>):> ># Key values used to pick minimum weight edge in cut> >key>=> [sys.maxsize]>*> self>.V> >parent>=> [>None>]>*> self>.V># Array to store constructed MST> ># Make key 0 so that this vertex is picked as first vertex> >key[>0>]>=> 0> >mstSet>=> [>False>]>*> self>.V> >parent[>0>]>=> ->1> # First node is always the root of> >for> cout>in> range>(>self>.V):> ># Pick the minimum distance vertex from> ># the set of vertices not yet processed.> ># u is always equal to src in first iteration> >u>=> self>.minKey(key, mstSet)> ># Put the minimum distance vertex in> ># the shortest path tree> >mstSet[u]>=> True> ># Update dist value of the adjacent vertices> ># of the picked vertex only if the current> ># distance is greater than new distance and> ># the vertex in not in the shortest path tree> >for> v>in> range>(>self>.V):> ># graph[u][v] is non zero only for adjacent vertices of m> ># mstSet[v] is false for vertices not yet included in MST> ># Update the key only if graph[u][v] is smaller than key[v]> >if> self>.graph[u][v]>>0> and> mstSet[v]>=>=> False> > >and> key[v]>>self>.graph[u][v]:> >key[v]>=> self>.graph[u][v]> >parent[v]>=> u> >self>.printMST(parent)> # Driver's code> if> __name__>=>=> '__main__'>:> >g>=> Graph(>5>)> >g.graph>=> [[>0>,>2>,>0>,>6>,>0>],> >[>2>,>0>,>3>,>8>,>5>],> >[>0>,>3>,>0>,>0>,>7>],> >[>6>,>8>,>0>,>0>,>9>],> >[>0>,>5>,>7>,>9>,>0>]]> >g.primMST()> # Contributed by Divyanshu Mehta> |
>
>
C#
// A C# program for Prim's Minimum> // Spanning Tree (MST) algorithm.> // The program is for adjacency> // matrix representation of the graph> using> System;> class> MST {> >// Number of vertices in the graph> >static> int> V = 5;> >// A utility function to find> >// the vertex with minimum key> >// value, from the set of vertices> >// not yet included in MST> >static> int> minKey(>int>[] key,>bool>[] mstSet)> >{> >// Initialize min value> >int> min =>int>.MaxValue, min_index = -1;> >for> (>int> v = 0; v if (mstSet[v] == false && key[v] min = key[v]; min_index = v; } return min_index; } // A utility function to print // the constructed MST stored in parent[] static void printMST(int[] parent, int[, ] graph) { Console.WriteLine('Edge Weight'); for (int i = 1; i Console.WriteLine(parent[i] + ' - ' + i + ' ' + graph[i, parent[i]]); } // Function to construct and // print MST for a graph represented // using adjacency matrix representation static void primMST(int[, ] graph) { // Array to store constructed MST int[] parent = new int[V]; // Key values used to pick // minimum weight edge in cut int[] key = new int[V]; // To represent set of vertices // included in MST bool[] mstSet = new bool[V]; // Initialize all keys // as INFINITE for (int i = 0; i key[i] = int.MaxValue; mstSet[i] = false; } // Always include first 1st vertex in MST. // Make key 0 so that this vertex is // picked as first vertex // First node is always root of MST key[0] = 0; parent[0] = -1; // The MST will have V vertices for (int count = 0; count // Pick the minimum key vertex // from the set of vertices // not yet included in MST int u = minKey(key, mstSet); // Add the picked vertex // to the MST Set mstSet[u] = true; // Update key value and parent // index of the adjacent vertices // of the picked vertex. Consider // only those vertices which are // not yet included in MST for (int v = 0; v // graph[u][v] is non zero only // for adjacent vertices of m // mstSet[v] is false for vertices // not yet included in MST Update // the key only if graph[u][v] is // smaller than key[v] if (graph[u, v] != 0 && mstSet[v] == false && graph[u, v] parent[v] = u; key[v] = graph[u, v]; } } // Print the constructed MST printMST(parent, graph); } // Driver's Code public static void Main() { int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 }, { 2, 0, 3, 8, 5 }, { 0, 3, 0, 0, 7 }, { 6, 8, 0, 0, 9 }, { 0, 5, 7, 9, 0 } }; // Print the solution primMST(graph); } } // This code is contributed by anuj_67.> |
>
>
Javascript
> // Number of vertices in the graph> let V = 5;> // A utility function to find the vertex with> // minimum key value, from the set of vertices> // not yet included in MST> function> minKey(key, mstSet)> {> >// Initialize min value> >let min = Number.MAX_VALUE, min_index;> >for> (let v = 0; v if (mstSet[v] == false && key[v] min = key[v], min_index = v; return min_index; } // A utility function to print the // constructed MST stored in parent[] function printMST(parent, graph) { document.write('Edge Weight' + ' '); for (let i = 1; i document.write(parent[i] + ' - ' + i + ' ' + graph[i][parent[i]] + ' '); } // Function to construct and print MST for // a graph represented using adjacency // matrix representation function primMST(graph) { // Array to store constructed MST let parent = []; // Key values used to pick minimum weight edge in cut let key = []; // To represent set of vertices included in MST let mstSet = []; // Initialize all keys as INFINITE for (let i = 0; i key[i] = Number.MAX_VALUE, mstSet[i] = false; // Always include first 1st vertex in MST. // Make key 0 so that this vertex is picked as first vertex. key[0] = 0; parent[0] = -1; // First node is always root of MST // The MST will have V vertices for (let count = 0; count { // Pick the minimum key vertex from the // set of vertices not yet included in MST let u = minKey(key, mstSet); // Add the picked vertex to the MST Set mstSet[u] = true; // Update key value and parent index of // the adjacent vertices of the picked vertex. // Consider only those vertices which are not // yet included in MST for (let v = 0; v // graph[u][v] is non zero only for adjacent vertices of m // mstSet[v] is false for vertices not yet included in MST // Update the key only if graph[u][v] is smaller than key[v] if (graph[u][v] && mstSet[v] == false && graph[u][v] parent[v] = u, key[v] = graph[u][v]; } // print the constructed MST printMST(parent, graph); } // Driver code let graph = [ [ 0, 2, 0, 6, 0 ], [ 2, 0, 3, 8, 5 ], [ 0, 3, 0, 0, 7 ], [ 6, 8, 0, 0, 9 ], [ 0, 5, 7, 9, 0 ] ]; // Print the solution primMST(graph); // This code is contributed by Dharanendra L V.> |
>
>Sortir
Edge Weight 0 - 1 2 1 - 2 3 0 - 3 6 1 - 4 5>
Analyse de la complexité de l'algorithme de Prim :
Complexité temporelle : O(V2), Si l'entrée le graphique est représenté à l'aide d'une liste de contiguïté , alors la complexité temporelle de l'algorithme de Prim peut être réduite à O(E * logV) à l'aide d'un tas binaire. Dans cette implémentation, nous considérons toujours que l'arbre couvrant commence à partir de la racine du graphique.
Espace auxiliaire : O(V)
Autres implémentations de l'algorithme de Prim :
Vous trouverez ci-dessous quelques autres implémentations de l'algorithme de Prim.
- Algorithme de Prim pour la représentation matricielle d'adjacence – Dans cet article, nous avons discuté de la méthode d’implémentation de l’algorithme de Prim si le graphe est représenté par une matrice de contiguïté.
- Algorithme de Prim pour la représentation de liste de contiguïté – Dans cet article, l'implémentation de l'algorithme de Prim est décrite pour les graphiques représentés par une liste de contiguïté.
- Algorithme de Prim utilisant la file d'attente prioritaire : Dans cet article, nous avons discuté d’une approche rapide pour implémenter l’algorithme de Prim.
APPROCHE OPTIMISÉE DE L’ALGORITHME DE PRIM :
Intuition
- Nous transformons la matrice de contiguïté en liste de contiguïté en utilisant Liste des tableaux
. - Ensuite, nous créons une classe Pair pour stocker le sommet et son poids.
- Nous trions la liste sur la base du poids le plus faible.
- Nous créons une file d'attente prioritaire et plaçons le premier sommet et son poids dans la file d'attente
- Ensuite, nous parcourons simplement ses bords et stockons le plus petit poids dans une variable appelée ans.
- Enfin après tout le sommet nous retournons l'ans.
Mise en œuvre
C++
#include> using> namespace> std;> typedef> pair<>int>,>int>>pi;> // Function to find sum of weights of edges of the Minimum Spanning Tree.> int> spanningTree(>int> V,>int> E,>int> edges[][3])> {> >// Create an adjacency list representation of the graph> >vectorint>> adj[V]; // Remplir la liste de contiguïté avec les arêtes et leurs poids pour (int i = 0; i int u = Edges[i][0]; int v = Edges[i][1]; int wt = Edges[i][2 ]; adj[u].push_back({v, wt}); adj[v].push_back({u, wt}); } // Crée une file d'attente prioritaire pour stocker les arêtes avec leurs poids priorité_queue pq; tableau visité pour garder une trace du vecteur des sommets visités |
>
>
Java
comment télécharger des vidéos youtube vlc
// A Java program for Prim's Minimum Spanning Tree (MST)> // algorithm. The program is for adjacency list> // representation of the graph> import> java.io.*;> import> java.util.*;> // Class to form pair> class> Pair>implements> Comparable> {> >int> v;> >int> wt;> >Pair(>int> v,>int> wt)> >{> >this>.v=v;> >this>.wt=wt;> >}> >public> int> compareTo(Pair that)> >{> >return> this>.wt-that.wt;> >}> }> class> GFG {> // Function of spanning tree> static> int> spanningTree(>int> V,>int> E,>int> edges[][])> >{> >ArrayList adj=>new> ArrayList();> >for>(>int> i=>0>;i { adj.add(new ArrayList()); } for(int i=0;i { int u=edges[i][0]; int v=edges[i][1]; int wt=edges[i][2]; adj.get(u).add(new Pair(v,wt)); adj.get(v).add(new Pair(u,wt)); } PriorityQueue pq = new PriorityQueue(); pq.add(new Pair(0,0)); int[] vis=new int[V]; int s=0; while(!pq.isEmpty()) { Pair node=pq.poll(); int v=node.v; int wt=node.wt; if(vis[v]==1) continue; s+=wt; vis[v]=1; for(Pair it:adj.get(v)) { if(vis[it.v]==0) { pq.add(new Pair(it.v,it.wt)); } } } return s; } // Driver code public static void main (String[] args) { int graph[][] = new int[][] {{0,1,5}, {1,2,3}, {0,2,1}}; // Function call System.out.println(spanningTree(3,3,graph)); } }> |
>
>
Python3
import> heapq> def> tree(V, E, edges):> ># Create an adjacency list representation of the graph> >adj>=> [[]>for> _>in> range>(V)]> ># Fill the adjacency list with edges and their weights> >for> i>in> range>(E):> >u, v, wt>=> edges[i]> >adj[u].append((v, wt))> >adj[v].append((u, wt))> ># Create a priority queue to store edges with their weights> >pq>=> []> ># Create a visited array to keep track of visited vertices> >visited>=> [>False>]>*> V> ># Variable to store the result (sum of edge weights)> >res>=> 0> ># Start with vertex 0> >heapq.heappush(pq, (>0>,>0>))> ># Perform Prim's algorithm to find the Minimum Spanning Tree> >while> pq:> >wt, u>=> heapq.heappop(pq)> >if> visited[u]:> >continue> ># Skip if the vertex is already visited> >res>+>=> wt> ># Add the edge weight to the result> >visited[u]>=> True> ># Mark the vertex as visited> ># Explore the adjacent vertices> >for> v, weight>in> adj[u]:> >if> not> visited[v]:> >heapq.heappush(pq, (weight, v))> ># Add the adjacent edge to the priority queue> >return> res> ># Return the sum of edge weights of the Minimum Spanning Tree> if> __name__>=>=> '__main__'>:> >graph>=> [[>0>,>1>,>5>],> >[>1>,>2>,>3>],> >[>0>,>2>,>1>]]> ># Function call> >print>(tree(>3>,>3>, graph))> |
>
>
C#
comment fonctionne un ordinateur
using> System;> using> System.Collections.Generic;> public> class> MinimumSpanningTree> {> >// Function to find sum of weights of edges of the Minimum Spanning Tree.> >public> static> int> SpanningTree(>int> V,>int> E,>int>[,] edges)> >{> >// Create an adjacency list representation of the graph> >Listint[]>> adj = new Listint[]>>(); pour (int i = 0; i { adj.Add (nouvelle liste |
>
>
Javascript
class PriorityQueue {> >constructor() {> >this>.heap = [];> >}> >enqueue(value) {> >this>.heap.push(value);> >let i =>this>.heap.length - 1;> >while> (i>0) {> >let j = Math.floor((i - 1) / 2);> >if> (>this>.heap[i][0]>=>this>.heap[j][0]) {> >break>;> >}> >[>this>.heap[i],>this>.heap[j]] = [>this>.heap[j],>this>.heap[i]];> >i = j;> >}> >}> >dequeue() {> >if> (>this>.heap.length === 0) {> >throw> new> Error(>'Queue is empty'>);> >}> >let i =>this>.heap.length - 1;> >const result =>this>.heap[0];> >this>.heap[0] =>this>.heap[i];> >this>.heap.pop();> >i--;> >let j = 0;> >while> (>true>) {> >const left = j * 2 + 1;> >if> (left>je) {> >break>;> >}> >const right = left + 1;> >let k = left;> >if> (right <= i &&>this>.heap[right][0] <>this>.heap[left][0]) {> >k = right;> >}> >if> (>this>.heap[j][0] <=>this>.heap[k][0]) {> >break>;> >}> >[>this>.heap[j],>this>.heap[k]] = [>this>.heap[k],>this>.heap[j]];> >j = k;> >}> >return> result;> >}> >get count() {> >return> this>.heap.length;> >}> }> function> spanningTree(V, E, edges) {> >// Create an adjacency list representation of the graph> >const adj =>new> Array(V).fill(>null>).map(() =>[]);> >// Fill the adjacency list with edges and their weights> >for> (let i = 0; i const [u, v, wt] = edges[i]; adj[u].push([v, wt]); adj[v].push([u, wt]); } // Create a priority queue to store edges with their weights const pq = new PriorityQueue(); // Create a visited array to keep track of visited vertices const visited = new Array(V).fill(false); // Variable to store the result (sum of edge weights) let res = 0; // Start with vertex 0 pq.enqueue([0, 0]); // Perform Prim's algorithm to find the Minimum Spanning Tree while (pq.count>0) { const p = pq.dequeue(); poids const = p[0]; // Poids du bord const u = p[1]; // Sommet connecté à l'arête if (visited[u]) { continue; // Ignorer si le sommet est déjà visité } res += wt; // Ajoutez le poids du bord au résultat visité[u] = true; // Marque le sommet comme visité // Explorez les sommets adjacents pour (const v of adj[u]) { // v[0] représente le sommet et v[1] représente le poids de l'arête if (!visited[v[0 ]]) { pq.enqueue([v[1], v[0]]); // Ajoute le bord adjacent à la file d'attente prioritaire } } } return res; // Renvoie la somme des poids des bords du Minimum Spanning Tree } // Exemple d'utilisation const graph = [[0, 1, 5], [1, 2, 3], [0, 2, 1]]; // Appel de fonction console.log(spanningTree(3, 3, graph));> |
>
>Sortir
4>
Analyse de la complexité de l'algorithme de Prim :
Complexité temporelle : O(E*log(E)) où E est le nombre d'arêtes
Espace auxiliaire : O(V^2) où V est le nombre de sommet
L'algorithme de Prim pour trouver l'arbre couvrant minimum (MST) :
Avantages :
- L’algorithme de Prim est assuré de trouver le MST dans un graphique connecté et pondéré.
- Il a une complexité temporelle de O (E log V) en utilisant un tas binaire ou tas de Fibonacci, où E est le nombre d'arêtes et V est le nombre de sommets.
- Il s'agit d'un algorithme relativement simple à comprendre et à mettre en œuvre par rapport à certains autres algorithmes MST.
Désavantages:
- Comme l’algorithme de Kruskal, l’algorithme de Prim peut être lent sur des graphes denses comportant de nombreuses arêtes, car il nécessite une itération sur toutes les arêtes au moins une fois.
- L'algorithme de Prim repose sur une file d'attente prioritaire, qui peut occuper de la mémoire supplémentaire et ralentir l'algorithme sur de très grands graphiques.
- Le choix du nœud de départ peut affecter la sortie MST, ce qui peut ne pas être souhaitable dans certaines applications.