У овом чланку ћемо разговарати о Примовом алгоритму. Уз алгоритам, видећемо и сложеност, рад, пример и имплементацију Примовог алгоритма.
Пре него што започнемо главну тему, требало би да разговарамо о основним и важним појмовима као што су разапињуће стабло и минимално разапињуће стабло.
Спаннинг трее - Разапињуће дрво је подграф неусмереног повезаног графа.
Минимално разапињуће дрво - Минимално разапињуће стабло се може дефинисати као разапињуће стабло у коме је збир тежина ивице минималан. Тежина разапињућег стабла је збир тежина датих ивицама разапињућег стабла.
Почнимо са главном темом.
Примов алгоритам је похлепни алгоритам који се користи за проналажење минималног обухвата стабла из графа. Примов алгоритам проналази подскуп ивица који укључује сваки врх графа тако да се збир тежина ивица може минимизирати.
Примов алгоритам почиње са једним чвором и истражује све суседне чворове са свим повезујућим ивицама на сваком кораку. Изабране су ивице са минималним тежинама које не узрокују циклусе у графу.
Како функционише примов алгоритам?
Примов алгоритам је похлепни алгоритам који почиње од једног темена и наставља да додаје ивице са најмањом тежином док се не постигне циљ. Кораци за имплементацију Примовог алгоритма су дати на следећи начин -
- Прво, морамо да иницијализујемо МСТ са насумично одабраним врхом.
- Сада морамо пронаћи све ивице које повезују стабло у горњем кораку са новим врховима. Од пронађених ивица изаберите минималну ивицу и додајте је стаблу.
- Поновите корак 2 док се не формира минимално разапињуће стабло.
Примене Примовог алгоритма су -
- Примов алгоритам се може користити у пројектовању мреже.
- Може се користити за прављење мрежних циклуса.
- Такође се може користити за полагање електричних каблова.
Пример Примовог алгоритма
Сада, да видимо рад Примовог алгоритма користећи пример. Биће лакше разумети примов алгоритам користећи пример.
Претпоставимо да је пондерисани график -
Корак 1 - Прво, морамо да изаберемо врх из горњег графа. Хајде да изаберемо Б.
јава стринг за цхар
Корак 2 - Сада морамо изабрати и додати најкраћу ивицу из темена Б. Постоје две ивице из темена Б које су од Б до Ц са тежином 10 и ивице Б у Д са тежином 4. Међу ивицама, ивица БД има минималну тежину . Дакле, додајте га у МСТ.
Корак 3 - Сада, опет, изаберите ивицу са минималном тежином међу свим осталим ивицама. У овом случају, ивице ДЕ и ЦД су такве ивице. Додајте их у МСТ и истражите суседне тачке Ц, тј. Е и А. Дакле, изаберите ивицу ДЕ и додајте је у МСТ.
Корак 4 - Сада изаберите ЦД са ивицом и додајте га у МСТ.
Корак 5 - Сада изаберите ивицу ЦА. Овде не можемо да изаберемо ивицу ЦЕ јер би то створило циклус на графу. Дакле, изаберите ивицу ЦА и додајте је у МСТ.
Дакле, граф произведен у кораку 5 је минимално разапињуће стабло датог графа. Цена МСТ-а је дата у наставку -
Цена МСТ = 4 + 2 + 1 + 3 = 10 јединица.
Алгоритам
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
Сложеност Примовог алгоритма
Сада, да видимо временску сложеност Примовог алгоритма. Време рада прим алгоритма зависи од употребе структуре података за граф и редоследа ивица. У табели испод су приказани неки избори -
| Структура података која се користи за минималну тежину ивице | Временска сложеност |
|---|---|
| Матрица суседности, линеарно претраживање | О(|В|2) |
| Листа суседности и бинарна гомила | О(|Е| лог |В|) |
| Листа суседности и Фибоначијева гомила | О(|Е|+ |В| лог |В|) |
Примов алгоритам се може једноставно имплементирати коришћењем матрице суседности или приказа графа листе суседности, а за додавање ивице са минималном тежином потребно је линеарно претраживање низа тежина. То захтева О(|В|2) време за трчање. Може се даље побољшати коришћењем имплементације гомиле да би се пронашле ивице минималне тежине у унутрашњој петљи алгоритма.
Временска сложеност прим алгоритма је О(Е логВ) или О(В логВ), где је Е број. ивица, а В је бр. врхова.
Имплементација Примовог алгоритма
Сада, да видимо имплементацију Примовог алгоритма.
Програм: Написати програм за имплементацију Примовог алгоритма у језику Ц.
#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;>