logo

TechCodeview

Крускалов алгоритам

У овом чланку ћемо разговарати о Крускаловом алгоритму. Овде ћемо такође видети сложеност, рад, пример и имплементацију Крускаловог алгоритма.

Али пре него што пређемо директно на алгоритам, прво треба да разумемо основне појмове као што су разапињуће стабло и минимално разапињуће стабло.

Спаннинг трее - Разапињуће дрво је подграф неусмереног повезаног графа.

Минимално разапињуће дрво - Минимално разапињуће стабло се може дефинисати као разапињуће стабло у коме је збир тежина ивице минималан. Тежина разапињућег стабла је збир тежина датих ивицама разапињућег стабла.

Сада, почнимо са главном темом.

Крускалов алгоритам се користи за проналажење минималног разапињућег стабла за повезани пондерисани граф. Главни циљ алгоритма је да пронађе подскуп ивица помоћу којих можемо прећи сваки врх графа. Следи похлепни приступ који проналази оптимално решење у свакој фази уместо да се фокусира на глобални оптимум.

Како функционише Крускалов алгоритам?

У Крускаловом алгоритму, почињемо од ивица са најмањом тежином и настављамо са додавањем ивица док се не постигне циљ. Кораци за имплементацију Крускаловог алгоритма су наведени на следећи начин -

  • Прво, сортирајте све ивице од мале тежине до високе.
  • Сада, узмите ивицу са најмањом тежином и додајте је разапињућем стаблу. Ако ивица која се додаје ствара циклус, одбаците ивицу.
  • Наставите да додајете ивице док не дођемо до свих врхова и створи се минимално разапињуће стабло.

Примене Крускаловог алгоритма су -

  • Крускалов алгоритам се може користити за постављање електричних инсталација између градова.
  • Може се користити за постављање ЛАН веза.

Пример Крускаловог алгоритма

Сада, да видимо како функционише Крускалов алгоритам користећи пример. Биће лакше разумети Крускалов алгоритам на примеру.

Претпоставимо да је пондерисани график -

Крускал

Тежина ивица горњег графикона је дата у табели испод -

Ивица АБ АЦ АД АЛИ пре нове ере ЦД ОФ
Тежина 1 7 10 5 3 4 2

Сада сортирајте горе наведене ивице у растућем редоследу њихових тежина.

Ивица АБ ОФ пре нове ере ЦД АЛИ АЦ АД
Тежина 1 2 3 4 5 7 10

Сада, хајде да почнемо да конструишемо минимално разапињуће стабло.

потхинени рам

Корак 1 - Прво додајте ивицу АБ са тежином 1 у МСТ.

Крускал

Корак 2 - Додајте ивицу ОФ са тежином 2 МСТ-у јер не ствара циклус.

Крускал

Корак 3 - Додајте ивицу пре нове ере са тежином 3 на МСТ, јер не ствара никакав циклус или петљу.

Крускал

Корак 4 - Сада изаберите ивицу ЦД са тежином 4 на МСТ, пошто не формира циклус.

Крускал

Корак 5 - Након тога, изаберите ивицу АЛИ са тежином 5. Укључивање ове ивице ће створити циклус, па га одбаците.

Корак 6 - Изаберите ивицу АЦ са тежином 7. Укључивање ове ивице ће створити циклус, па га одбаците.

Корак 7 - Изаберите ивицу АД са тежином 10. Укључивање ове ивице ће такође створити циклус, па га одбаците.

Дакле, коначно минимално разапињуће стабло добијено из датог пондерисаног графа коришћењем Крускаловог алгоритма је -

Крускал

Цена МСТ-а је = АБ + ДЕ + БЦ + ЦД = 1 + 2 + 3 + 4 = 10.

Сада, број ивица у горњем стаблу једнак је броју темена минус 1. Дакле, алгоритам се овде зауставља.

Алгоритам

 Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree. Step 2: Create a set E that contains all the edges of the graph. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning Step 4: Remove an edge from E with minimum weight Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the forest F (for combining two trees into one tree). ELSE Discard the edge Step 6: END

Сложеност Крускаловог алгоритма

Сада, да видимо временску сложеност Крускаловог алгоритма.

    Временска сложеност
    Временска сложеност Крускаловог алгоритма је О(Е логЕ) или О(В логВ), где је Е број. ивица, а В је бр. врхова.

Имплементација Крускаловог алгоритма

Сада, да видимо имплементацију Крускаловог алгоритма.

Програм: Написати програм за имплементацију Крускаловог алгоритма у Ц++.

 #include #include using namespace std; const int MAX = 1e4 + 5; int id[MAX], nodes, edges; pair <long long, pair> p[MAX]; void init() { for(int i = 0;i <max;++i) id[i]="i;" } int root(int x) { while(id[x] !="x)" id[x]="id[id[x]];" x="id[x];" return x; void union1(int x, y) p="root(x);" q="root(y);" id[p]="id[q];" long kruskal(pair<long long, pair> p[]) { int x, y; long long cost, minimumCost = 0; for(int i = 0;i <edges;++i) { x="p[i].second.first;" y="p[i].second.second;" cost="p[i].first;" if(root(x) !="root(y))" minimumcost +="cost;" union1(x, y); } return minimumcost; int main() x, y; long weight, cost, init(); cout <> nodes &gt;&gt; edges; for(int i = 0;i <edges;++i) { cout<> x &gt;&gt; y &gt;&gt; weight; p[i] = make_pair(weight, make_pair(x, y)); } sort(p, p + edges); minimumCost = kruskal(p); cout &lt;<'minimum cost is '<< minimumcost << endl; return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/kruskals-algorithm-6.webp" alt="Kruskal"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></'minimum></edges;++i)></edges;++i)></max;++i)></long>