I den här artikeln kommer vi att diskutera prim:s algoritm. Tillsammans med algoritmen kommer vi också att se komplexiteten, arbetet, exemplet och implementeringen av prims algoritm.

Innan vi börjar med huvudämnet bör vi diskutera de grundläggande och viktiga termerna som spaning tree och minimum spaning tree.

Spanning Tree - Ett spännträd är subgrafen till en oriktad sammankopplad graf.

Minsta spännvidd träd - Minsta spännträd kan definieras som spännträdet där summan av kantens vikter är minimum. Vikten av spännträdet är summan av vikterna som ges till kanterna av spännträdet.

Låt oss nu börja huvudämnet.

Prims algoritm är en girig algoritm som används för att hitta det minsta spännträdet från en graf. Prims algoritm hittar delmängden av kanter som inkluderar varje vertex i grafen så att summan av kanternas vikter kan minimeras.

Prims algoritm börjar med den enda noden och utforskar alla intilliggande noder med alla anslutningskanter vid varje steg. Kanterna med de minimala vikterna som inte orsakar några cykler i grafen valdes ut.

Hur fungerar prim:s algoritm?

Prims algoritm är en girig algoritm som utgår från en vertex och fortsätter att lägga till kanterna med minsta vikt tills målet är nått. Stegen för att implementera prim:s algoritm ges enligt följande -

• Först måste vi initiera en MST med den slumpmässigt valda vertexen.
• Nu måste vi hitta alla kanter som förbinder trädet i steget ovan med de nya hörnen. Från de hittade kanterna väljer du minsta kanten och lägger till den i trädet.
• Upprepa steg 2 tills det minsta spännträdet bildas.

Tillämpningarna av prims algoritm är -

• Prims algoritm kan användas i nätverksdesign.
• Den kan användas för att skapa nätverkscykler.
• Den kan också användas för att lägga ner elektriska ledningar.

Exempel på prims algoritm

Låt oss nu se hur prims algoritm fungerar med ett exempel. Det blir lättare att förstå prim:s algoritm med hjälp av ett exempel.

Antag att en viktad graf är -

Steg 1 - Först måste vi välja en vertex från grafen ovan. Låt oss välja B.

hur man öppnar en fil med java

Steg 2 - Nu måste vi välja och lägga till den kortaste kanten från vertex B. Det finns två kanter från vertex B som är B till C med vikt 10 och kant B till D med vikt 4. Bland kanterna har kanten BD minsta vikt . Så lägg till det i MST.

Steg 3 - Välj nu igen kanten med minsta vikt bland alla andra kanter. I detta fall är kanterna DE och CD sådana kanter. Lägg till dem i MST och utforska intill C, dvs E och A. Så välj kanten DE och lägg till den i MST.

Steg 4 - Välj nu kant-CD:n och lägg till den i MST.

Steg 5 - Välj nu kanten CA. Här kan vi inte välja kanten CE eftersom det skulle skapa en cykel till grafen. Så välj kanten CA och lägg till den i MST.

Så, grafen som produceras i steg 5 är det minsta spännträdet i den givna grafen. Kostnaden för MST anges nedan -

Kostnad för MST = 4 + 2 + 1 + 3 = 10 enheter.

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 

Komplexiteten hos Prims algoritm

Låt oss nu se tidskomplexiteten hos Prims algoritm. Körtiden för prim-algoritmen beror på användningen av datastrukturen för grafen och kanternas ordning. Tabellen nedan visar några val -

Tidskomplexitet

Prims algoritm kan enkelt implementeras genom att använda grannmatrisen eller representationen av granslistans graf, och för att lägga till kanten med minsta vikt krävs linjär sökning av en rad vikter. Det kräver O(|V|²) körtid. Det kan förbättras ytterligare genom att använda implementeringen av heap för att hitta minimiviktskanterna i algoritmens inre loop.

Tidskomplexiteten för primens algoritm är O(E logV) eller O(V logV), där E är no. av kanter, och V är nr. av hörn.

Implementering av Prims algoritm

Låt oss nu se implementeringen av prims algoritm.

Program: Skriv ett program för att implementera prims algoritm i C-språk.

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