TechCodeview

U ovom ćemo članku raspravljati o prim algoritmu. Uz algoritam, također ćemo vidjeti složenost, rad, primjer i implementaciju algoritma prim.

Prije nego započnemo glavnu temu, trebali bismo raspraviti osnovne i važne pojmove kao što su razapinjuće stablo i minimalno razapinjuće stablo.

Razapinjuće stablo - Razapinjuće stablo je podgraf neusmjerenog povezanog grafa.

Minimalno razapinjuće stablo - Minimalno razapinjuće stablo može se definirati kao razapinjuće stablo u kojem je zbroj težina ruba minimalan. Težina razapinjućeg stabla zbroj je težina dodijeljenih rubovima razapinjućeg stabla.

Sada, započnimo glavnu temu.

Primov algoritam je pohlepni algoritam koji se koristi za pronalaženje minimalnog razapinjućeg stabla iz grafa. Primov algoritam pronalazi podskup bridova koji uključuje svaki vrh grafa tako da se zbroj težina bridova može minimizirati.

Primov algoritam počinje s jednim čvorom i istražuje sve susjedne čvorove sa svim spojnim rubovima u svakom koraku. Odabrani su rubovi s minimalnim težinama koji ne uzrokuju cikluse u grafu.

Kako radi primarni algoritam?

Primov algoritam je pohlepan algoritam koji počinje od jednog vrha i nastavlja dodavati rubove s najmanjom težinom dok se ne postigne cilj. Koraci za implementaciju primovog algoritma dani su kako slijedi -

• Prvo, moramo inicijalizirati MST s nasumično odabranim vrhom.
• Sada moramo pronaći sve rubove koji spajaju stablo u gornjem koraku s novim vrhovima. Među pronađenim rubovima odaberite najmanji rub i dodajte ga stablu.
• Ponovite korak 2 dok se ne formira minimalno razapinjuće stablo.

Primjene primovog algoritma su -

• Primov algoritam može se koristiti u projektiranju mreže.
• Može se koristiti za izradu mrežnih ciklusa.
• Također se može koristiti za polaganje električnih kabela.

Primjer primovog algoritma

Sada, pogledajmo rad primovog algoritma koristeći primjer. Bit će lakše razumjeti prim algoritam koristeći primjer.

Pretpostavimo da je ponderirani graf -

Korak 1 - Prvo, moramo odabrati vrh iz gornjeg grafa. Izaberimo B.

pretvaranje niza u java

Korak 2 - Sada moramo odabrati i dodati najkraći brid iz vrha B. Postoje dva brida iz vrha B koji su od B do C s težinom 10 i brid B do D s težinom 4. Među bridovima, brid BD ima minimalnu težinu . Dakle, dodajte ga u MST.

Korak 3 - Sada, opet, odaberite rub s minimalnom težinom među svim ostalim rubovima. U ovom slučaju bridovi DE i CD su takvi bridovi. Dodajte ih MST-u i istražite susjedni dio C, tj. E i A. Dakle, odaberite rub DE i dodajte ga MST-u.

Korak 4 - Sada odaberite rubni CD i dodajte ga u MST.

Korak 5 - Sada odaberite rub CA. Ovdje ne možemo odabrati rub CE jer bi on stvorio ciklus na grafu. Dakle, odaberite rubni CA i dodajte ga u MST.

Dakle, graf proizveden u koraku 5 je minimalno razapinjuće stablo danog grafa. Cijena MST-a navedena je u nastavku -

Trošak MST = 4 + 2 + 1 + 3 = 10 jedinica.

Algoritam

 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 

Složenost Primovog algoritma

Sada, da vidimo vremensku složenost Primovog algoritma. Vrijeme rada primovog algoritma ovisi o korištenju strukture podataka za graf i rasporedu rubova. Donja tablica prikazuje neke izbore -

Vremenska složenost

Primov algoritam može se jednostavno implementirati korištenjem matrice susjedstva ili prikaza grafa popisa susjedstva, a dodavanje ruba s minimalnom težinom zahtijeva linearno pretraživanje niza težina. Zahtijeva O(|V|²) trajanje. Može se dodatno poboljšati upotrebom implementacije gomile za pronalaženje rubova minimalne težine u unutarnjoj petlji algoritma.

Vremenska složenost primovog algoritma je O(E logV) ili O(V logV), gdje je E broj. rubova, a V je br. od vrhova.

Implementacija Primovog algoritma

Sada, da vidimo implementaciju primovog algoritma.

Program: Napišite program za implementaciju prima algoritma u C jeziku.

 #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;>