Šiame straipsnyje aptarsime prim algoritmą. Kartu su algoritmu taip pat pamatysime prim algoritmo sudėtingumą, veikimą, pavyzdį ir įgyvendinimą.

Prieš pradėdami pagrindinę temą, turėtume aptarti pagrindinius ir svarbius terminus, tokius kaip besitęsiantis medis ir minimalus besitęsiantis medis.

besitęsiantis medis - Apimamasis medis yra neorientuoto sujungto grafo pografas.

Mažiausias besitęsiantis medis – Minimalus apimantis medis gali būti apibrėžtas kaip apimantis medis, kuriame briaunos svorių suma yra minimali. Tvirtinimo medžio svoris yra svorių, pateiktų besitęsiančio medžio kraštams, suma.

Dabar pradėkime nuo pagrindinės temos.

Primo algoritmas yra gobšus algoritmas, kuris naudojamas ieškant minimalaus apimančio medžio iš grafiko. Prim algoritmas suranda briaunų poaibį, apimantį kiekvieną grafo viršūnę, kad būtų galima sumažinti briaunų svorių sumą.

Prim algoritmas prasideda nuo vieno mazgo ir kiekviename žingsnyje ištiria visus gretimus mazgus su visomis jungiamomis briaunomis. Buvo pasirinktos briaunos su minimaliais svoriais, nesukeliančiais ciklų grafike.

Kaip veikia prim algoritmas?

Primo algoritmas yra gobšus algoritmas, kuris prasideda nuo vienos viršūnės ir toliau sudeda mažiausio svorio briaunas, kol pasiekiamas tikslas. Prim algoritmo įgyvendinimo žingsniai pateikiami taip:

• Pirmiausia turime inicijuoti MST su atsitiktinai pasirinkta viršūne.
• Dabar turime rasti visus kraštus, jungiančius medį aukščiau pateiktame žingsnyje su naujomis viršūnėmis. Iš rastų kraštų pasirinkite minimalų kraštą ir pridėkite jį prie medžio.
• Kartokite 2 veiksmą, kol bus suformuotas minimalus besitęsiantis medis.

Prim algoritmo taikymas yra:

• Prim algoritmas gali būti naudojamas projektuojant tinklą.
• Jis gali būti naudojamas tinklo ciklams kurti.
• Jis taip pat gali būti naudojamas elektros laidų kabeliams tiesti.

Prim algoritmo pavyzdys

Dabar pažiūrėkime, kaip veikia prim algoritmas naudojant pavyzdį. Prim algoritmą bus lengviau suprasti naudojant pavyzdį.

Tarkime, kad svertinis grafikas yra -

1 žingsnis - Pirmiausia turime pasirinkti viršūnę iš aukščiau pateikto grafiko. Pasirinkime B.

kaip konvertuoti eilutę į char

2 žingsnis - Dabar turime pasirinkti ir pridėti trumpiausią briauną iš viršūnės B. Yra dvi briaunos iš viršūnės B, kurios yra nuo B iki C, kurių svoris yra 10, ir nuo B iki D su svoriu 4. Tarp kraštų kraštas BD turi mažiausią svorį . Taigi, pridėkite jį prie MST.

3 veiksmas – Dabar vėl pasirinkite kraštą su minimaliu svoriu tarp visų kitų kraštų. Šiuo atveju kraštai DE ir CD yra tokie kraštai. Pridėkite juos prie MST ir ištirkite gretimus C, ty E ir A. Taigi, pasirinkite kraštą DE ir pridėkite jį prie MST.

4 veiksmas – Dabar pasirinkite krašto kompaktinį diską ir pridėkite jį prie MST.

5 veiksmas – Dabar pasirinkite kraštą CA. Čia negalime pasirinkti krašto CE, nes tai sukurtų grafiko ciklą. Taigi, pasirinkite krašto CA ir pridėkite jį prie MST.

Taigi 5 žingsnyje sudarytas grafikas yra mažiausias nurodyto grafiko apimantis medis. MST kaina nurodyta žemiau -

MST kaina = 4 + 2 + 1 + 3 = 10 vnt.

Algoritmas

 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 

Primo algoritmo sudėtingumas

Dabar pažiūrėkime, koks yra Prim algoritmo sudėtingumas. Prim algoritmo veikimo laikas priklauso nuo duomenų struktūros naudojimo grafikui ir briaunų išdėstymo. Žemiau esančioje lentelėje pateikiami keli pasirinkimai -

Laiko sudėtingumas

Prim algoritmą galima paprasčiausiai įgyvendinti naudojant gretimų matricą arba gretimų sąrašo grafiką, o norint pridėti kraštą su minimaliu svoriu, reikia tiesiškai ieškoti svorių masyvo. Tam reikia O(|V|²) veikimo laikas. Jį galima dar patobulinti naudojant krūvos įgyvendinimą, kad būtų galima rasti minimalius svorio kraštus vidinėje algoritmo kilpoje.

Pirminio algoritmo laiko sudėtingumas yra O(E logV) arba O(V logV), kur E yra Nr. briaunų, o V yra Nr. viršūnių.

Primo algoritmo įgyvendinimas

Dabar pažiūrėkime, kaip įgyvendinamas prim algoritmas.

Programa: Parašykite programą prim algoritmui įgyvendinti C kalba.

 #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&apos;s all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>