I denne artikel vil vi diskutere prim's algoritme. Sammen med algoritmen vil vi også se kompleksiteten, virkemåden, eksemplet og implementeringen af prims algoritme.
Inden vi starter hovedemnet, bør vi diskutere de grundlæggende og vigtige udtryk såsom spændingstræ og minimum spændingstræ.
Spændende træ - Et spændingstræ er undergrafen af en urettet forbundet graf.
Minimum spændvidde træ - Minimum spændingstræ kan defineres som spændingstræet, hvor summen af kantens vægte er minimum. Vægten af spændingstræet er summen af vægtene givet til kanterne af spændingstræet.
Lad os nu starte hovedemnet.
Prims algoritme er en grådig algoritme, der bruges til at finde det mindste spændingstræ fra en graf. Prims algoritme finder den delmængde af kanter, der inkluderer hvert hjørne af grafen, således at summen af vægtene af kanterne kan minimeres.
Prims algoritme starter med den enkelte node og udforsker alle de tilstødende noder med alle forbindelseskanterne ved hvert trin. Kanterne med de minimale vægte, der ikke forårsagede nogen cyklusser i grafen, blev valgt.
Hvordan fungerer prim'ens algoritme?
Prims algoritme er en grådig algoritme, der starter fra det ene toppunkt og fortsætter med at tilføje kanterne med den mindste vægt, indtil målet er nået. Trinene til at implementere prim's algoritme er givet som følger -
- Først skal vi initialisere en MST med det tilfældigt valgte toppunkt.
- Nu skal vi finde alle de kanter, der forbinder træet i ovenstående trin med de nye hjørner. Fra de fundne kanter skal du vælge minimumskanten og tilføje den til træet.
- Gentag trin 2, indtil minimumspændingstræet er dannet.
Anvendelserne af prim's algoritme er -
- Prims algoritme kan bruges i netværksdesign.
- Det kan bruges til at lave netværkscyklusser.
- Den kan også bruges til at nedlægge elektriske ledninger.
Eksempel på prims algoritme
Lad os nu se, hvordan prim's algoritme fungerer ved hjælp af et eksempel. Det vil være lettere at forstå prim's algoritme ved hjælp af et eksempel.
Antag, at en vægtet graf er -
Trin 1 - Først skal vi vælge et toppunkt fra ovenstående graf. Lad os vælge B.
java8 funktioner
Trin 2 - Nu skal vi vælge og tilføje den korteste kant fra top B. Der er to kanter fra top B, som er B til C med vægt 10 og kant B til D med vægt 4. Blandt kanterne har kanten BD minimum vægt . Så tilføj det til MST.
Trin 3 - Nu skal du igen vælge kanten med den mindste vægt blandt alle de andre kanter. I dette tilfælde er kanterne DE og CD sådanne kanter. Tilføj dem til MST og udforsk den tilstødende af C, dvs. E og A. Så vælg kanten DE og føj den til MST.
Trin 4 - Vælg nu kant-cd'en, og tilføj den til MST.
Trin 5 - Vælg nu kanten CA. Her kan vi ikke vælge kanten CE, da det ville skabe en cyklus til grafen. Så vælg kanten CA og føj den til MST.
Så grafen fremstillet i trin 5 er minimumspændingstræet for den givne graf. Prisen for MST er angivet nedenfor -
Pris for MST = 4 + 2 + 1 + 3 = 10 enheder.
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
Kompleksiteten af Prims algoritme
Lad os nu se tidskompleksiteten af Prims algoritme. Køretiden for prim's algoritme afhænger af brugen af datastrukturen til grafen og rækkefølgen af kanter. Nedenstående tabel viser nogle valg -
| Datastruktur brugt til minimum kantvægt | Tidskompleksitet |
|---|---|
| Adjacency matrix, lineær søgning | O(|V|2) |
| Adjacency liste og binær heap | O(|E| log |V|) |
| Adjacency liste og Fibonacci heap | O(|E|+ |V| log |V|) |
Prims algoritme kan nemt implementeres ved at bruge tilstødende matrix eller tilstødende liste graf repræsentation, og at tilføje kanten med minimum vægt kræver lineær søgning af en række vægte. Det kræver O(|V|2) løbe tid. Det kan forbedres yderligere ved at bruge implementeringen af heap til at finde minimumsvægtkanterne i algoritmens indre sløjfe.
Tidskompleksiteten af prim's algoritme er O(E logV) eller O(V logV), hvor E er no. af kanter, og V er nr. af hjørner.
Implementering af Prims algoritme
Lad os nu se implementeringen af prim's algoritme.
Program: Skriv et program til at implementere prim's algoritme i C-sprog.
#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;>