Ebben a cikkben a prim algoritmusát tárgyaljuk. Az algoritmus mellett látni fogjuk a prim algoritmus bonyolultságát, működését, példáját és megvalósítását is.
A fő téma megkezdése előtt meg kell beszélnünk az alapvető és fontos kifejezéseket, mint például a feszítőfa és a minimális feszítőfa.
Feszítőfának - A feszítőfa egy irányítatlan összefüggő gráf részgráfja.
Minimális feszülő fa - Minimális feszítőfa az a feszítőfa, amelyben az él súlyainak összege minimális. A feszítőfa súlya a feszítőfa éleihez adott súlyok összege.
Most pedig kezdjük a fő témával.
Prim algoritmusa egy mohó algoritmus, amelyet arra használnak, hogy megtalálják a minimális feszítőfát egy gráfból. A Prim algoritmusa megkeresi az élek azon részhalmazát, amely a gráf minden csúcsát tartalmazza úgy, hogy az élek súlyának összege minimalizálható.
A Prim algoritmusa az egyetlen csomóponttal kezdődik, és minden lépésben feltárja az összes szomszédos csomópontot az összes csatlakozó éllel együtt. A minimális súlyú élek, amelyek nem okoznak ciklust a gráfban, kerültek kiválasztásra.
Hogyan működik a prim algoritmusa?
A Prim algoritmusa egy mohó algoritmus, amely egy csúcsból indul ki, és a cél eléréséig folytatja a legkisebb súlyú élek összeadását. A prim algoritmus megvalósításának lépései a következők:
- Először is inicializálnunk kell egy MST-t a véletlenszerűen kiválasztott csúcsponttal.
- Most meg kell találnunk az összes élt, amely összeköti a fát a fenti lépésben az új csúcsokkal. A talált élek közül válassza ki a minimális élt, és adja hozzá a fához.
- Ismételje meg a 2. lépést, amíg létre nem jön a minimális fedőfa.
A prim algoritmus alkalmazásai a következők:
- A Prim-algoritmus a hálózattervezésben használható.
- Használható hálózati ciklusok készítésére.
- Elektromos vezetékek lefektetésére is használható.
Példa a prim algoritmusára
Most nézzük meg a prim algoritmus működését egy példa segítségével. Egy példa segítségével könnyebb lesz megérteni a prim algoritmusát.
Tegyük fel, hogy egy súlyozott gráf -
1. lépés - Először is ki kell választanunk egy csúcsot a fenti gráfból. Válasszuk a B-t.
jelentkezzen ki a google fiókból androidon
2. lépés - Most ki kell választanunk és hozzá kell adnunk a B csúcsból a legrövidebb élt. A B csúcsból két él van, amelyek B-től C-ig 10 súllyal és B-től D-ig 4-es súllyal. Az élek közül a BD élnek van a legkisebb súlya. . Tehát adja hozzá az MST-hez.
3. lépés - Most ismét válassza ki a minimális súlyú élt az összes többi él közül. Ebben az esetben a DE és a CD élek ilyen élek. Adja hozzá őket az MST-hez, és fedezze fel a szomszédos C-t, azaz E-t és A-t. Tehát válassza ki a DE élt, és adja hozzá az MST-hez.
4. lépés - Most válassza ki az él CD-t, és adja hozzá az MST-hez.
5. lépés - Most válassza ki az él CA-t. Itt nem tudjuk kiválasztani a CE élt, mivel az ciklust hozna létre a gráfhoz. Tehát válassza ki az él CA-t, és adja hozzá az MST-hez.
Tehát az 5. lépésben előállított gráf az adott gráf minimális feszítőfája. Az MST költsége alább látható -
Az MST költsége = 4 + 2 + 1 + 3 = 10 egység.
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
Prim algoritmusának összetettsége
Most pedig lássuk a Prim-algoritmus időbeli összetettségét. A prim algoritmusának futási ideje a gráf adatszerkezetének használatától és az élek sorrendjétől függ. Az alábbi táblázat néhány választási lehetőséget mutat -
| A minimális élsúlyhoz használt adatstruktúra | Idő összetettsége |
|---|---|
| Szomszédsági mátrix, lineáris keresés | O(|V|2) |
| Szomszédsági lista és bináris kupac | O(|E| log |V|) |
| Szomszédsági lista és Fibonacci kupac | O(|E|+ |V| log |V|) |
A Prim algoritmusa egyszerűen megvalósítható a szomszédsági mátrix vagy szomszédsági lista gráf reprezentációjával, és a minimális súllyal rendelkező él hozzáadásához súlyok tömbjének lineáris keresése szükséges. O(|V|2) futási idő. Tovább javítható a kupac megvalósításával, hogy megtaláljuk a minimális súlyú éleket az algoritmus belső ciklusában.
A prim algoritmusának időbonyolultsága O(E logV) vagy O(V logV), ahol E a nem. élek, és V a sz. csúcsok közül.
A Prim-algoritmus megvalósítása
Most pedig lássuk a prim algoritmus megvalósítását.
Program: Írjon programot a prim algoritmus megvalósítására C nyelven.
#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;>