V tomto článku budeme diskutovať o primovom algoritme. Spolu s algoritmom uvidíme aj zložitosť, fungovanie, príklad a implementáciu primovho algoritmu.

Pred začatím hlavnej témy by sme si mali prebrať základné a dôležité pojmy ako kostra a minimálna kostra.

Spanning tree - Kostra je podgrafom neorientovaného súvislého grafu.

Minimálny kostrový strom - Minimálny kostra môže byť definovaná ako kostra, v ktorej je súčet váh hrany minimálny. Hmotnosť kostry je súčet váh pridelených okrajom kostry.

Teraz začnime hlavnou témou.

Primov algoritmus je chamtivý algoritmus, ktorý sa používa na nájdenie minimálneho kostry z grafu. Primov algoritmus nájde podmnožinu hrán, ktorá zahŕňa každý vrchol grafu, takže súčet váh hrán môže byť minimalizovaný.

Primov algoritmus začína jedným uzlom a v každom kroku skúma všetky susediace uzly so všetkými spojovacími hranami. Boli vybraté hrany s minimálnymi váhami, ktoré nespôsobovali žiadne cykly v grafe.

Ako funguje primov algoritmus?

Primov algoritmus je chamtivý algoritmus, ktorý začína od jedného vrcholu a pokračuje v pridávaní hrán s najmenšou váhou, kým sa nedosiahne cieľ. Kroky na implementáciu primovho algoritmu sú uvedené nasledovne -

• Najprv musíme inicializovať MST s náhodne vybraným vrcholom.
• Teraz musíme nájsť všetky hrany, ktoré spájajú strom vo vyššie uvedenom kroku s novými vrcholmi. Z nájdených hrán vyberte minimálnu hranu a pridajte ju do stromu.
• Opakujte krok 2, kým sa nevytvorí minimálny kostra.

Aplikácie primovho algoritmu sú -

• Primov algoritmus je možné použiť pri návrhu siete.
• Môže sa použiť na vytváranie sieťových cyklov.
• Môže sa použiť aj na položenie elektrických káblov.

Príklad primovho algoritmu

Teraz sa pozrime na fungovanie primovho algoritmu na príklade. Pomocou príkladu bude jednoduchšie pochopiť primárny algoritmus.

Predpokladajme, že vážený graf je -

Krok 1 - Najprv si musíme vybrať vrchol z vyššie uvedeného grafu. Vyberme si B.

zahŕňajú programovanie c

Krok 2 - Teraz si musíme vybrať a pridať najkratšiu hranu z vrcholu B. Z vrcholu B sú dve hrany, ktoré sú B až C s váhou 10 a hrana B až D s váhou 4. Medzi hranami má hrana BD minimálnu váhu. . Pridajte ho teda do MST.

Krok 3 - Teraz opäť vyberte hranu s minimálnou hmotnosťou spomedzi všetkých ostatných hrán. V tomto prípade sú takýmito okrajmi okraje DE a CD. Pridajte ich do MST a preskúmajte susedné C, t.j. E a A. Vyberte teda okraj DE a pridajte ho do MST.

Krok 4 - Teraz vyberte okrajové CD a pridajte ho do MST.

Krok 5 - Teraz vyberte okrajovú CA. Tu nemôžeme vybrať hranu CE, pretože by vytvorila cyklus do grafu. Vyberte teda okrajovú CA a pridajte ju do MST.

Takže graf vytvorený v kroku 5 je minimálnou kostrou daného grafu. Cena MST je uvedená nižšie -

Náklady na MST = 4 + 2 + 1 + 3 = 10 jednotiek.

Algoritmus

 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 

Zložitosť Primovho algoritmu

Teraz sa pozrime na časovú zložitosť Primovho algoritmu. Doba chodu algoritmu prim závisí od použitia dátovej štruktúry pre graf a zoradenia hrán. Nižšie uvedená tabuľka zobrazuje niektoré možnosti -

Časová zložitosť

Primov algoritmus možno jednoducho implementovať pomocou matice susednosti alebo grafu zoznamu susednosti a pridať hranu s minimálnou váhou vyžaduje lineárne vyhľadávanie poľa váh. Vyžaduje O(|V|²) doba chodu. Dá sa ďalej vylepšiť použitím implementácie haldy na nájdenie minimálnych váhových hrán vo vnútornej slučke algoritmu.

Časová zložitosť primárneho algoritmu je O(E logV) alebo O(V logV), kde E je číslo. hrán a V je č. z vrcholov.

Implementácia Primovho algoritmu

Teraz sa pozrime na implementáciu primovho algoritmu.

Program: Napíšte program na implementáciu primovho algoritmu v jazyku 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&apos;s all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>