TechCodeview

V tomto článku budeme diskutovat o primově algoritmu. Spolu s algoritmem uvidíme také složitost, fungování, příklad a implementaci primova algoritmu.

Než začneme s hlavním tématem, měli bychom probrat základní a důležité pojmy, jako je kostra a minimální kostra.

Spanning tree - Kostra je podgraf neorientovaného souvislého grafu.

Minimální kostra - Minimální kostru lze definovat jako kostru, ve které je součet vah hrany minimální. Hmotnost kostry je součtem vah daných okrajům kostry.

Nyní začněme hlavním tématem.

Primův algoritmus je chamtivý algoritmus, který se používá k nalezení minimální kostry z grafu. Primův algoritmus najde podmnožinu hran, která zahrnuje každý vrchol grafu, takže součet vah hran lze minimalizovat.

Primův algoritmus začíná jediným uzlem a v každém kroku prozkoumává všechny sousední uzly se všemi spojovacími hranami. Byly vybrány hrany s minimálními váhami způsobujícími žádné cykly v grafu.

Jak funguje primův algoritmus?

Primův algoritmus je chamtivý algoritmus, který začíná od jednoho vrcholu a pokračuje v přidávání hran s nejmenší váhou, dokud není dosaženo cíle. Kroky k implementaci primova algoritmu jsou uvedeny následovně -

• Nejprve musíme inicializovat MST s náhodně vybraným vrcholem.
• Nyní musíme najít všechny hrany, které spojují strom ve výše uvedeném kroku s novými vrcholy. Z nalezených hran vyberte minimální hranu a přidejte ji do stromu.
• Opakujte krok 2, dokud se nevytvoří minimální kostra.

Aplikace primova algoritmu jsou -

• Primův algoritmus lze použít při návrhu sítě.
• Může být použit k vytváření síťových cyklů.
• Může být také použit pro položení elektrických kabelů.

Příklad primova algoritmu

Nyní se podívejme na fungování primova algoritmu na příkladu. Na příkladu bude snazší pochopit primův algoritmus.

Předpokládejme, že vážený graf je -

Krok 1 - Nejprve si musíme vybrat vrchol z výše uvedeného grafu. Vyberme si B.

včetně programování c

Krok 2 - Nyní musíme vybrat a přidat nejkratší hranu z vrcholu B. Z vrcholu B jsou dvě hrany, které jsou B až C s váhou 10 a hrana B až D s váhou 4. Mezi hranami má hrana BD minimální váhu. . Přidejte jej tedy do MST.

Krok 3 - Nyní opět vyberte hranu s minimální hmotností ze všech ostatních hran. V tomto případě jsou hrany DE a CD takové hrany. Přidejte je do MST a prozkoumejte sousedící C, tj. E a A. Vyberte tedy hranu DE a přidejte ji do MST.

Krok 4 - Nyní vyberte okrajové CD a přidejte jej do MST.

Krok 5 - Nyní vyberte okrajovou CA. Zde nemůžeme vybrat hranu CE, protože by vytvořila cyklus do grafu. Vyberte tedy okrajovou CA a přidejte ji do MST.

Graf vytvořený v kroku 5 je tedy minimální kostrou daného grafu. Cena MST je uvedena níže -

Náklady na MST = 4 + 2 + 1 + 3 = 10 jednotek.

Algoritmus

 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 

Složitost Primova algoritmu

Nyní se podívejme na časovou složitost Primova algoritmu. Doba běhu primárního algoritmu závisí na použití datové struktury pro graf a uspořádání hran. Níže uvedená tabulka ukazuje některé možnosti -

Časová složitost

Primův algoritmus lze jednoduše implementovat pomocí matice sousednosti nebo grafu se seznamem sousedství a přidání hrany s minimální váhou vyžaduje lineární vyhledávání pole vah. Vyžaduje O(|V|²) doba provozu. Lze jej dále zlepšit použitím implementace haldy k nalezení okrajů minimální hmotnosti ve vnitřní smyčce algoritmu.

Časová složitost primárního algoritmu je O(E logV) nebo O(V logV), kde E je číslo. hran a V je ne. z vrcholů.

Implementace Primova algoritmu

Nyní se podívejme na implementaci primova algoritmu.

Program: Napište program pro implementaci primova algoritmu v jazyce 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;>