TechCodeview

V tem članku bomo razpravljali o algoritmu prim. Ob algoritmu si bomo ogledali tudi kompleksnost, delovanje, primer in implementacijo primovega algoritma.

Preden začnemo z glavno temo, bi morali razpravljati o osnovnih in pomembnih izrazih, kot sta vpeto drevo in minimalno vpeto drevo.

Vpeto drevo - Vpeto drevo je podgraf neusmerjenega povezanega grafa.

Najmanjše vpeto drevo - Minimalno vpeto drevo lahko definiramo kot vpeto drevo, v katerem je vsota uteži roba minimalna. Teža vpetega drevesa je vsota uteži robov vpetega drevesa.

Zdaj pa začnimo glavno temo.

Primov algoritem je požrešen algoritem, ki se uporablja za iskanje najmanjšega vpetega drevesa iz grafa. Primov algoritem najde podmnožico robov, ki vključuje vsako vozlišče grafa, tako da je vsoto uteži robov mogoče minimizirati.

Primov algoritem se začne z enim vozliščem in raziskuje vsa sosednja vozlišča z vsemi povezovalnimi robovi na vsakem koraku. Izbrani so bili robovi z minimalnimi utežmi, ki ne povzročajo ciklov v grafu.

Kako deluje primarjev algoritem?

Primov algoritem je požrešen algoritem, ki se začne iz enega vozlišča in dodaja robove z najmanjšo težo, dokler ni dosežen cilj. Koraki za implementacijo primovega algoritma so podani na naslednji način -

• Najprej moramo inicializirati MST z naključno izbranim vozliščem.
• Zdaj moramo najti vse robove, ki povezujejo drevo v zgornjem koraku z novimi vozlišči. Med najdenimi robovi izberite najmanjši rob in ga dodajte drevesu.
• Ponavljajte korak 2, dokler ni oblikovano minimalno vpeto drevo.

Aplikacije primovega algoritma so -

• Primov algoritem se lahko uporablja pri načrtovanju omrežja.
• Lahko se uporablja za izdelavo omrežnih ciklov.
• Uporablja se lahko tudi za polaganje električnih kablov.

Primer primovega algoritma

Zdaj pa si na primeru oglejmo delovanje primovega algoritma. Primov algoritem bo lažje razumeti na primeru.

Recimo, da je uteženi graf -

Korak 1 - Najprej moramo izbrati vozlišče iz zgornjega grafa. Izberimo B.

java veljavni identifikatorji

2. korak - Sedaj moramo izbrati in dodati najkrajši rob iz oglišča B. Obstajata dva roba iz oglišča B, ki sta B proti C s težo 10 in rob B proti D s težo 4. Med robovi ima rob BD najmanjšo težo . Torej, dodajte ga v MST.

3. korak - Sedaj ponovno izberite rob z najmanjšo težo med vsemi drugimi robovi. V tem primeru sta robova DE in CD takšna robova. Dodajte jih v MST in raziščite sosednji del C, tj. E in A. Torej izberite rob DE in ga dodajte v MST.

4. korak - Zdaj izberite robni CD in ga dodajte v MST.

5. korak - Zdaj izberite rob CA. Tukaj ne moremo izbrati roba CE, saj bi ustvaril cikel na grafu. Torej izberite robni CA in ga dodajte v MST.

Graf, izdelan v koraku 5, je torej minimalno vpeto drevo danega grafa. Stroški MST so navedeni spodaj -

Stroški MST = 4 + 2 + 1 + 3 = 10 enot.

Algoritem

 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 

Kompleksnost Primovega algoritma

Zdaj pa poglejmo časovno kompleksnost Primovega algoritma. Čas delovanja primovega algoritma je odvisen od uporabe podatkovne strukture za graf in vrstnega reda robov. Spodnja tabela prikazuje nekaj izbir -

Časovna zapletenost

Primov algoritem je mogoče preprosto implementirati z uporabo matrike sosednosti ali predstavitve grafa seznama sosednosti, dodajanje roba z najmanjšo težo pa zahteva linearno iskanje niza uteži. Zahteva O(|V|²) trajanje. Lahko ga še izboljšamo z uporabo izvajanja kopice za iskanje robov najmanjše teže v notranji zanki algoritma.

Časovna kompleksnost primovega algoritma je O(E logV) ali O(V logV), kjer je E št. robov, V pa je št. vozlišč.

Izvedba Primovega algoritma

Zdaj pa poglejmo implementacijo primovega algoritma.

Program: Napišite program za implementacijo primovega algoritma v jeziku 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;>