TechCodeview

Šajā rakstā mēs apspriedīsim prim algoritmu. Kopā ar algoritmu mēs redzēsim arī prim algoritma sarežģītību, darbību, piemēru un ieviešanu.

Pirms galvenās tēmas sākšanas mums jāapspriež pamata un svarīgi termini, piemēram, aptverošais koks un minimālais aptverošais koks.

aptverošs koks - Izvēršanas koks ir nevirzīta savienota grafika apakšgrafs.

Minimālais platuma koks - Minimālo stiepuma koku var definēt kā stiepuma koku, kurā malas svaru summa ir minimāla. Aptverošā koka svars ir to svaru summa, kas piešķirti stiepjošā koka malām.

Tagad sāksim galveno tēmu.

Prima algoritms ir mantkārīgs algoritms, ko izmanto, lai no grafika atrastu minimālo aptverošo koku. Prima algoritms atrod malu apakškopu, kas ietver katru grafa virsotni tā, lai malu svaru summu varētu samazināt līdz minimumam.

Prim algoritms sākas ar vienu mezglu un katrā solī izpēta visus blakus esošos mezglus ar visām savienojošajām malām. Tika atlasītas malas ar minimālo svaru, kas nerada grafikā ciklus.

Kā darbojas prim algoritms?

Prima algoritms ir mantkārīgs algoritms, kas sākas no vienas virsotnes un turpina pievienot malas ar mazāko svaru, līdz tiek sasniegts mērķis. Prim algoritma ieviešanas soļi ir norādīti šādi:

• Pirmkārt, mums ir jāinicializē MST ar nejauši izvēlētu virsotni.
• Tagad mums ir jāatrod visas malas, kas savieno koku iepriekš minētajā darbībā ar jaunajām virsotnēm. No atrastajām malām atlasiet minimālo malu un pievienojiet to kokam.
• Atkārtojiet 2. darbību, līdz ir izveidots minimālais aptverošais koks.

Prim algoritma pielietojumi ir -

• Prima algoritmu var izmantot tīklu projektēšanā.
• To var izmantot, lai izveidotu tīkla ciklus.
• To var izmantot arī elektrisko vadu kabeļu novietošanai.

Prim algoritma piemērs

Tagad apskatīsim prim algoritma darbību, izmantojot piemēru. Prim algoritmu būs vieglāk saprast, izmantojot piemēru.

Pieņemsim, ka svērtais grafiks ir -

1. darbība — Pirmkārt, mums ir jāizvēlas virsotne no iepriekš minētā grafika. Izvēlēsimies B.

powershell mazāks par vai vienāds ar

2. darbība — Tagad mums ir jāizvēlas un jāpievieno īsākā mala no virsotnes B. No virsotnes B ir divas malas, kas ir no B līdz C ar svaru 10 un no B līdz D ar svaru 4. Starp malām malai BD ir minimālais svars. . Tātad, pievienojiet to MST.

3. darbība — Tagad atkal izvēlieties malu ar minimālo svaru starp visām pārējām malām. Šajā gadījumā malas DE un CD ir šādas malas. Pievienojiet tos MST un izpētiet blakus esošos C, t.i., E un A. Tātad, atlasiet malu DE un pievienojiet to MST.

4. darbība — Tagad atlasiet malas kompaktdisku un pievienojiet to MST.

5. darbība — Tagad izvēlieties malu CA. Šeit mēs nevaram atlasīt malu CE, jo tas radītu diagrammas ciklu. Tātad, izvēlieties malas CA un pievienojiet to MST.

Tātad 5. solī izveidotais grafiks ir dotā grafika minimālais aptverošais koks. MST izmaksas ir norādītas zemāk -

MST izmaksas = 4 + 2 + 1 + 3 = 10 vienības.

Algoritms

 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 

Prima algoritma sarežģītība

Tagad apskatīsim Prima algoritma laika sarežģītību. Prim algoritma darbības laiks ir atkarīgs no datu struktūras izmantošanas grafikam un malu secības. Zemāk tabulā ir parādītas dažas izvēles iespējas -

Laika sarežģītība

Prima algoritmu var vienkārši ieviest, izmantojot blakus esošu matricu vai blakus esošo sarakstu diagrammas attēlojumu, un, lai pievienotu malu ar minimālo svaru, ir jāmeklē lineāri svaru masīvs. Tam nepieciešams O(|V|²) darbības laiks. To var vēl vairāk uzlabot, izmantojot kaudzes ieviešanu, lai atrastu minimālās svara malas algoritma iekšējā cilpā.

Prim algoritma laika sarežģītība ir O(E logV) vai O(V logV), kur E ir nr. no malām, un V ir nr. no virsotnēm.

Prima algoritma realizācija

Tagad apskatīsim prim algoritma ieviešanu.

Programma: Uzrakstiet programmu prim algoritma ieviešanai C valodā.

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