I denne artikkelen vil vi diskutere primens algoritme. Sammen med algoritmen vil vi også se kompleksiteten, virkemåten, eksempelet og implementeringen av prims algoritme.
Før vi starter hovedemnet, bør vi diskutere de grunnleggende og viktige begrepene som spenntre og minimum spenntre.
Spanning tre - Et spenningstre er undergrafen til en urettet tilkoblet graf.
Minimum spannende tre - Minimum spenntre kan defineres som spenntreet der summen av vektene til kanten er minimum. Vekten til spenntreet er summen av vektene gitt til kantene på spenntreet.
La oss nå starte hovedemnet.
Prims algoritme er en grådig algoritme som brukes til å finne minimumspenningstreet fra en graf. Prims algoritme finner delsettet av kanter som inkluderer hvert toppunkt i grafen, slik at summen av vektene til kantene kan minimeres.
Prims algoritme starter med enkeltnoden og utforsker alle tilstøtende noder med alle forbindelseskantene ved hvert trinn. Kantene med minimale vekter som forårsaker ingen sykluser i grafen ble valgt.
Hvordan fungerer primens algoritme?
Prims algoritme er en grådig algoritme som starter fra ett toppunkt og fortsetter å legge til kantene med den minste vekten til målet er nådd. Trinnene for å implementere prim-algoritmen er gitt som følger -
- Først må vi initialisere en MST med det tilfeldig valgte toppunktet.
- Nå må vi finne alle kantene som forbinder treet i trinnet ovenfor med de nye hjørnene. Fra kantene som ble funnet, velg minimumskanten og legg den til treet.
- Gjenta trinn 2 til minimumspenningstreet er dannet.
Anvendelsene av prims algoritme er -
- Prims algoritme kan brukes i nettverksdesign.
- Den kan brukes til å lage nettverkssykluser.
- Den kan også brukes til å legge ned elektriske ledninger.
Eksempel på prims algoritme
La oss nå se hvordan prims algoritme fungerer ved å bruke et eksempel. Det vil være lettere å forstå primens algoritme ved å bruke et eksempel.
Anta at en vektet graf er -
Trinn 1 - Først må vi velge et toppunkt fra grafen ovenfor. La oss velge B.
typescript datotype
Steg 2 - Nå må vi velge og legge til den korteste kanten fra toppunkt B. Det er to kanter fra toppunkt B som er B til C med vekt 10 og kant B til D med vekt 4. Blant kantene har kanten BD minimum vekt . Så legg den til i MST.
Trinn 3 - Nå, igjen, velg kanten med minimum vekt blant alle de andre kantene. I dette tilfellet er kantene DE og CD slike kanter. Legg dem til MST og utforsk den tilstøtende av C, dvs. E og A. Så velg kanten DE og legg den til MST.
Trinn 4 - Velg nå kant-CDen og legg den til MST.
Trinn 5 - Velg nå kanten CA. Her kan vi ikke velge kanten CE da det ville skape en syklus til grafen. Så velg kanten CA og legg den til MST.
Så, grafen produsert i trinn 5 er minimumsspenningstreet i den gitte grafen. Kostnaden for MST er gitt nedenfor -
Kostnad for MST = 4 + 2 + 1 + 3 = 10 enheter.
Algoritme
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
Kompleksiteten til Prims algoritme
La oss nå se tidskompleksiteten til Prims algoritme. Kjøretiden til prim-algoritmen avhenger av bruk av datastrukturen for grafen og rekkefølgen av kanter. Tabellen nedenfor viser noen valg -
| Datastruktur brukt for minimum kantvekt | Tidskompleksitet |
|---|---|
| Adjacency matrise, lineær søking | O(|V|2) |
| Adjacency liste og binær haug | O(|E| log |V|) |
| Adjacency-liste og Fibonacci-haug | O(|E|+ |V| log |V|) |
Prims algoritme kan enkelt implementeres ved å bruke tilstøtningsmatrisen eller grafrepresentasjonen av tilstøtende liste, og for å legge til kanten med minimumsvekt kreves lineært søk av en rekke vekter. Det krever O(|V|2) driftstid. Det kan forbedres ytterligere ved å bruke implementeringen av heap for å finne minimum vektkanter i den indre sløyfen av algoritmen.
Tidskompleksiteten til primens algoritme er O(E logV) eller O(V logV), der E er no. av kanter, og V er nr. av hjørner.
Implementering av Prims algoritme
La oss nå se implementeringen av prims algoritme.
Program: Skriv et program for å implementere prims algoritme i C-språk.
#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;>