En aquest article, parlarem de l'algorisme del prim. Juntament amb l'algoritme, també veurem la complexitat, el funcionament, l'exemple i la implementació de l'algorisme de prim.
Abans de començar el tema principal, hauríem de parlar dels termes bàsics i importants com ara spanning tree i spanning tree mínim.
arbre spanning - Un arbre spanning és el subgraf d'un graf connectat no dirigit.
Arbre spanning mínim - L'arbre spanning mínim es pot definir com l'arbre spanning en el qual la suma dels pesos de la vora és mínima. El pes de l'arbre spanning és la suma dels pesos donats a les vores de l'arbre spanning.
Ara, comencem el tema principal.
Algoritme de Prim és un algorisme cobdiciós que s'utilitza per trobar l'arbre d'abast mínim a partir d'un gràfic. L'algorisme de Prim troba el subconjunt d'arestes que inclou cada vèrtex del gràfic de manera que la suma dels pesos de les arestes es pugui minimitzar.
L'algorisme de Prim comença amb el node únic i explora tots els nodes adjacents amb totes les vores de connexió a cada pas. S'han seleccionat les vores amb els pesos mínims que no provoquen cicles al gràfic.
Com funciona l'algoritme del prim?
L'algoritme de Prim és un algorisme cobdiciós que parteix d'un vèrtex i continua afegint les arestes amb el pes més petit fins que s'assoleix l'objectiu. Els passos per implementar l'algorisme de prim es donen de la següent manera:
- En primer lloc, hem d'iniciar un MST amb el vèrtex escollit aleatòriament.
- Ara, hem de trobar totes les vores que connecten l'arbre al pas anterior amb els nous vèrtexs. De les vores trobades, seleccioneu la vora mínima i afegiu-la a l'arbre.
- Repetiu el pas 2 fins que es formi l'arbre mínim.
Les aplicacions de l'algorisme de prim són -
- L'algoritme de Prim es pot utilitzar en el disseny de xarxes.
- Es pot utilitzar per fer cicles de xarxa.
- També es pot utilitzar per col·locar cables elèctrics.
Exemple de l'algorisme de prim
Ara, vegem el funcionament de l'algorisme de prim utilitzant un exemple. Serà més fàcil entendre l'algorisme del prim utilitzant un exemple.
Suposem que un gràfic ponderat és -
Pas 1 - En primer lloc, hem de triar un vèrtex del gràfic anterior. Triem B.
com convertir str a int
Pas 2 - Ara, hem de triar i afegir l'aresta més curta del vèrtex B. Hi ha dues arestes del vèrtex B que són de B a C amb pes 10 i arestes de B a D amb pes 4. Entre les arestes, l'aresta BD té el pes mínim. . Per tant, afegiu-lo al MST.
Pas 3 - Ara, de nou, tria la vora amb el pes mínim entre totes les altres vores. En aquest cas, les vores DE i CD són aquestes vores. Afegiu-los a MST i exploreu l'adjacent de C, és a dir, E i A. Per tant, seleccioneu la vora DE i afegiu-lo a l'MST.
Pas 4 - Ara, seleccioneu el CD de vora i afegiu-lo a l'MST.
Pas 5 - Ara, trieu la vora CA. Aquí, no podem seleccionar la vora CE ja que crearia un cicle al gràfic. Per tant, trieu l'edge CA i afegiu-lo a l'MST.
Per tant, el gràfic produït al pas 5 és l'arbre abastant mínim del gràfic donat. El cost del MST es mostra a continuació:
Cost de MST = 4 + 2 + 1 + 3 = 10 unitats.
Algorisme
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
Complexitat de l'algorisme de Prim
Ara, vegem la complexitat temporal de l'algoritme de Prim. El temps d'execució de l'algorisme del prim depèn de l'ús de l'estructura de dades per al gràfic i l'ordenació de les arestes. La taula següent mostra algunes opcions:
| Estructura de dades utilitzada per al pes mínim de la vora | Complexitat temporal |
|---|---|
| Matriu d'adjacència, cerca lineal | O(|V|2) |
| Llista d'adjacència i munt binari | O(|E| log |V|) |
| Llista d'adjacència i pila de Fibonacci | O(|E|+ |V| log |V|) |
L'algorisme de Prim es pot implementar simplement utilitzant la matriu d'adjacència o la representació del gràfic de la llista d'adjacència, i per afegir la vora amb el pes mínim requereix la cerca lineal d'una matriu de pesos. Requereix O(|V|2) temps d'execució. Es pot millorar encara més utilitzant la implementació d'heap per trobar les vores de pes mínim al bucle intern de l'algorisme.
La complexitat temporal de l'algorisme del prim és O(E logV) o O(V logV), on E és el núm. d'arestes, i V és el núm. de vèrtexs.
Implementació de l'algorisme de Prim
Ara, vegem la implementació de l'algorisme de prim.
Programa: Escriu un programa per implementar l'algorisme de prim en llenguatge 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;>