Tässä artikkelissa käsittelemme primin algoritmia. Algoritmin ohella näemme myös prim-algoritmin monimutkaisuuden, toimivuuden, esimerkin ja toteutuksen.
Ennen kuin aloitamme pääaiheen, meidän tulisi keskustella perus- ja tärkeistä termeistä, kuten virittävä puu ja minimivirittävä puu.
Virtaava puu - Virittävä puu on suuntaamattoman yhdistetyn graafin osagraafi.
Vähimmäisvirtapuu - Pienin virittävä puu voidaan määritellä virittäväksi puuksi, jossa reunan painojen summa on pienin. Virittävän puun paino on virittävän puun reunoihin annettujen painojen summa.
Aloitetaan nyt pääaihe.
Primin algoritmi on ahne algoritmi, jota käytetään etsimään kaaviosta pienin virittävä puu. Primin algoritmi löytää reunojen osajoukon, joka sisältää graafin jokaisen kärjen siten, että reunojen painojen summa voidaan minimoida.
Primin algoritmi alkaa yhdestä solmusta ja tutkii jokaisessa vaiheessa kaikkia vierekkäisiä solmuja kaikilla yhdistävillä reunoilla. Valittiin reunat, joiden painot ovat minimaaliset, jotka eivät aiheuta syklejä kaaviossa.
Kuinka primin algoritmi toimii?
Primin algoritmi on ahne algoritmi, joka alkaa yhdestä kärjestä ja jatkaa pienimmän painoisten reunojen lisäämistä, kunnes tavoite saavutetaan. Vaiheet primin algoritmin toteuttamiseksi on annettu seuraavasti:
- Ensin meidän on alustettava MST satunnaisesti valitulla kärjellä.
- Nyt meidän on löydettävä kaikki reunat, jotka yhdistävät puun yllä olevassa vaiheessa uusiin pisteisiin. Valitse löydetyistä reunoista minimireuna ja lisää se puuhun.
- Toista vaihe 2, kunnes pienin virittävä puu on muodostettu.
Primin algoritmin sovellukset ovat -
- Primin algoritmia voidaan käyttää verkkosuunnittelussa.
- Sitä voidaan käyttää verkkojaksojen tekemiseen.
- Sitä voidaan käyttää myös sähköjohtojen asennukseen.
Esimerkki primin algoritmista
Katsotaanpa nyt primin algoritmin toimintaa esimerkin avulla. Esimerkin avulla on helpompi ymmärtää primin algoritmi.
Oletetaan, että painotettu kaavio on -
Vaihe 1 - Ensin meidän on valittava kärki yllä olevasta kaaviosta. Valitaan B.
mikä on svn checkout
Vaihe 2 - Nyt meidän on valittava ja lisättävä kärjestä B lyhin reuna. Huipusta B on kaksi reunaa, jotka ovat B:stä C painoon 10 ja reunaan B:hen D painolla 4. Reunoista reunalla BD on vähimmäispaino . Joten lisää se MST:hen.
Vaihe 3 - Valitse nyt jälleen se reuna, jonka paino on pienin kaikkien muiden reunojen joukosta. Tässä tapauksessa reunat DE ja CD ovat tällaisia reunoja. Lisää ne MST:hen ja tutki C:n viereisiä eli E:tä ja A:ta. Valitse siis reuna DE ja lisää se MST:hen.
Vaihe 4 - Valitse nyt reuna-CD ja lisää se MST:hen.
Vaihe 5 - Valitse nyt reuna CA. Tässä emme voi valita reunaa CE, koska se loisi syklin kuvaajaan. Valitse siis reuna CA ja lisää se MST:hen.
Vaiheessa 5 tuotettu graafi on siis annetun graafin pienin virittävä puu. MST:n hinta on annettu alla -
MST:n hinta = 4 + 2 + 1 + 3 = 10 yksikköä.
Algoritmi
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
Primin algoritmin monimutkaisuus
Katsotaan nyt Primin algoritmin aikamonimutkaisuus. Alkuperäisen algoritmin ajoaika riippuu graafin tietorakenteen käytöstä ja reunojen järjestyksestä. Alla oleva taulukko näyttää joitain vaihtoehtoja -
| Vähimmäisreunapainolle käytetty tietorakenne | Aika monimutkaisuus |
|---|---|
| Vierekkäisyysmatriisi, lineaarinen haku | O(|V|2) |
| Vierekkäisyysluettelo ja binäärikasa | O(|E| log |V|) |
| Vierekkäisyysluettelo ja Fibonacci-kasa | O(|E|+ |V| log |V|) |
Primin algoritmi voidaan yksinkertaisesti toteuttaa käyttämällä viereisyysmatriisia tai viereisyysluettelograafin esitystä, ja reunan lisääminen minimipainolla vaatii lineaarista hakua painojen joukosta. Se vaatii O(|V|2) käyntiaika. Sitä voidaan parantaa edelleen käyttämällä kasan toteutusta etsimään minimipainoreunat algoritmin sisäsilmukasta.
Alkuperäisen algoritmin aikakompleksisuus on O(E logV) tai O(V logV), missä E on no. reunoista, ja V on nro. pisteistä.
Primin algoritmin toteutus
Katsotaanpa nyt primin algoritmin toteutusta.
Ohjelmoida: Kirjoita ohjelma prim-algoritmin toteuttamiseksi C-kielellä.
#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;>