În acest articol, vom discuta despre algoritmul primului. Împreună cu algoritmul, vom vedea și complexitatea, funcționarea, exemplul și implementarea algoritmului prim.

Înainte de a începe subiectul principal, ar trebui să discutăm termenii de bază și importanți, cum ar fi spanning tree și spanning tree minim.

Arborele spanning - Un arbore de întindere este subgraful unui graf conectat nedirecționat.

Arborele de întindere minim - Arborele de întindere minim poate fi definit ca arborele de întindere în care suma greutăților marginii este minimă. Greutatea arborelui spanning este suma greutăților date marginilor arborelui spanning.

Acum, să începem subiectul principal.

Algoritmul lui Prim este un algoritm lacom care este folosit pentru a găsi arborele de acoperire minim dintr-un grafic. Algoritmul lui Prim găsește submulțimea muchiilor care include fiecare vârf al graficului astfel încât suma greutăților muchiilor să poată fi minimizată.

Algoritmul lui Prim începe cu un singur nod și explorează toate nodurile adiacente cu toate marginile de legătură la fiecare pas. Au fost selectate muchiile cu greutățile minime care nu provoacă cicluri în grafic.

Cum funcționează algoritmul primului?

Algoritmul lui Prim este un algoritm lacom care începe de la un vârf și continuă să adauge muchiile cu cea mai mică greutate până când obiectivul este atins. Pașii de implementare a algoritmului primului sunt dați după cum urmează -

• În primul rând, trebuie să inițializam un MST cu vârful ales aleatoriu.
• Acum, trebuie să găsim toate muchiile care conectează arborele în pasul de mai sus cu noile vârfuri. Din marginile găsite, selectați marginea minimă și adăugați-o în arbore.
• Repetați pasul 2 până când se formează arborele care se întinde minim.

Aplicațiile algoritmului prim sunt -

• Algoritmul lui Prim poate fi utilizat în proiectarea rețelelor.
• Poate fi folosit pentru a face cicluri de rețea.
• Poate fi folosit și pentru așezarea cablurilor electrice.

Exemplu de algoritm prim

Acum, să vedem funcționarea algoritmului lui prim folosind un exemplu. Va fi mai ușor de înțeles algoritmul primului folosind un exemplu.

Să presupunem că un grafic ponderat este -

Pasul 1 - În primul rând, trebuie să alegem un vârf din graficul de mai sus. Să alegem B.

câini de raft

Pasul 2 - Acum, trebuie să alegem și să adăugăm cea mai scurtă muchie de la vârful B. Există două muchii de la vârful B care sunt B la C cu greutatea 10 și muchia B la D cu greutatea 4. Dintre muchii, muchia BD are greutatea minimă . Deci, adăugați-l la MST.

Pasul 3 - Acum, din nou, alegeți muchia cu greutatea minimă dintre toate celelalte margini. În acest caz, muchiile DE și CD sunt astfel de muchii. Adăugați-le în MST și explorați adiacentul lui C, adică E și A. Deci, selectați marginea DE și adăugați-o la MST.

Pasul 4 - Acum, selectați CD-ul edge și adăugați-l la MST.

Pasul 5 - Acum, alegeți marginea CA. Aici, nu putem selecta marginea CE, deoarece ar crea un ciclu către grafic. Deci, alegeți marginea CA și adăugați-o la MST.

Deci, graficul produs la pasul 5 este arborele de acoperire minim al graficului dat. Costul MST este prezentat mai jos -

Costul MST = 4 + 2 + 1 + 3 = 10 unități.

Algoritm

 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 

Complexitatea algoritmului lui Prim

Acum, să vedem complexitatea în timp a algoritmului lui Prim. Timpul de rulare al algoritmului primului depinde de utilizarea structurii de date pentru grafic și de ordonarea muchiilor. Tabelul de mai jos arată câteva opțiuni -

Complexitatea timpului

Algoritmul lui Prim poate fi implementat pur și simplu folosind matricea de adiacență sau reprezentarea grafică a listei de adiacență, iar pentru a adăuga marginea cu greutatea minimă necesită căutarea liniară a unei matrice de greutăți. Este nevoie de O(|V|²) timpul pentru alergat. Poate fi îmbunătățit în continuare prin utilizarea implementării heap-ului pentru a găsi marginile minime ale greutății în bucla interioară a algoritmului.

Complexitatea temporală a algoritmului primului este O(E logV) sau O(V logV), unde E este nr. de muchii, iar V este nr. de vârfuri.

Implementarea algoritmului lui Prim

Acum, să vedem implementarea algoritmului lui prim.

Program: Scrieți un program pentru a implementa algoritmul prim în limbajul 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;>