In dit artikel bespreken we het algoritme van de prim. Naast het algoritme zullen we ook de complexiteit, werking, voorbeeld en implementatie van het algoritme van prim zien.
Voordat we met het hoofdonderwerp beginnen, moeten we de fundamentele en belangrijke termen bespreken, zoals opspannende boom en minimaal opspannende boom.
Overspannende boom - Een spanning tree is de subgraaf van een ongerichte verbonden graaf.
Minimaal overspannende boom - De minimaal opspannende boom kan worden gedefinieerd als de opspannende boom waarin de som van de gewichten van de rand minimaal is. Het gewicht van de opspannende boom is de som van de gewichten die aan de randen van de opspannende boom worden gegeven.
Laten we nu beginnen met het hoofdonderwerp.
Het algoritme van Prim is een hebzuchtig algoritme dat wordt gebruikt om de minimaal opspannende boom uit een grafiek te vinden. Het algoritme van Prim vindt de subset van randen die elk hoekpunt van de grafiek omvat, zodat de som van de gewichten van de randen kan worden geminimaliseerd.
Het algoritme van Prim begint met het enkele knooppunt en onderzoekt bij elke stap alle aangrenzende knooppunten met alle verbindingsranden. De randen met de minimale gewichten die geen cycli in de grafiek veroorzaken, zijn geselecteerd.
Hoe werkt het algoritme van de prim?
Het algoritme van Prim is een hebzuchtig algoritme dat begint bij één hoekpunt en doorgaat met het toevoegen van de randen met het kleinste gewicht totdat het doel is bereikt. De stappen om het algoritme van prim te implementeren worden als volgt gegeven:
- Eerst moeten we een MST initialiseren met het willekeurig gekozen hoekpunt.
- Nu moeten we alle randen vinden die de boom in de bovenstaande stap verbinden met de nieuwe hoekpunten. Selecteer uit de gevonden randen de minimale rand en voeg deze toe aan de boom.
- Herhaal stap 2 totdat de minimaal opspannende boom is gevormd.
De toepassingen van het algoritme van prim zijn -
- Het algoritme van Prim kan worden gebruikt bij het ontwerpen van netwerken.
- Het kan worden gebruikt om netwerkcycli te maken.
- Het kan ook worden gebruikt voor het leggen van elektrische bedradingskabels.
Voorbeeld van het algoritme van prim
Laten we nu de werking van het algoritme van prim bekijken aan de hand van een voorbeeld. Het zal gemakkelijker zijn om het algoritme van de prim te begrijpen aan de hand van een voorbeeld.
Stel dat een gewogen grafiek is:
Stap 1 - Eerst moeten we een hoekpunt uit de bovenstaande grafiek kiezen. Laten we B kiezen.
kat timpf gewicht
Stap 2 - Nu moeten we de kortste rand van hoekpunt B kiezen en toevoegen. Er zijn twee randen van hoekpunt B die B tot C zijn met gewicht 10 en rand B tot D met gewicht 4. Van de randen heeft rand BD het minimale gewicht . Voeg het dus toe aan de MST.
Stap 3 - Kies nu opnieuw de rand met het minimale gewicht tussen alle andere randen. In dit geval zijn de randen DE en CD dergelijke randen. Voeg ze toe aan MST en verken de aangrenzende gebieden van C, d.w.z. E en A. Selecteer dus de rand DE en voeg deze toe aan de MST.
Stap 4 - Selecteer nu de edge-CD en voeg deze toe aan de MST.
Stap 5 - Kies nu de rand CA. Hier kunnen we de rand CE niet selecteren, omdat dit een cyclus naar de grafiek zou creëren. Kies dus de edge-CA en voeg deze toe aan de MST.
De grafiek die in stap 5 wordt geproduceerd, is dus de minimaal opspannende boom van de gegeven grafiek. De kosten van de MST worden hieronder gegeven -
Kosten van MST = 4 + 2 + 1 + 3 = 10 eenheden.
Algoritme
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
Complexiteit van het algoritme van Prim
Laten we nu eens kijken naar de tijdscomplexiteit van het algoritme van Prim. De looptijd van het prim-algoritme hangt af van het gebruik van de datastructuur voor de grafiek en de volgorde van de randen. Onderstaande tabel toont enkele keuzes -
| Datastructuur gebruikt voor het minimale randgewicht | Tijdcomplexiteit |
|---|---|
| Nabijheidsmatrix, lineair zoeken | O(|V|2) |
| Aangrenzende lijst en binaire heap | O(|E| loggen |V|) |
| Aangrenzende lijst en Fibonacci-heap | O(|E|+ |V| loggen |V|) |
Het algoritme van Prim kan eenvoudig worden geïmplementeerd door gebruik te maken van de grafiekweergave van de aangrenzende matrix of de aangrenzende lijst, en om de rand met het minimale gewicht toe te voegen, is het lineair zoeken naar een reeks gewichten vereist. Het vereist O(|V|2) looptijd. Het kan verder worden verbeterd door de implementatie van heap te gebruiken om de minimale gewichtsranden in de binnenste lus van het algoritme te vinden.
De tijdscomplexiteit van het algoritme van prim is O(E logV) of O(V logV), waarbij E het nee is. van randen, en V is het nee. van hoekpunten.
Implementatie van het algoritme van Prim
Laten we nu eens kijken naar de implementatie van het algoritme van prim.
Programma: Schrijf een programma om het algoritme van prim in C-taal te implementeren.
#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's all about the article. Hope, the article will be helpful and informative to you.</p> <hr></vertices;>