TechCodeview

Šiame straipsnyje aptarsime Kruskal algoritmą. Čia taip pat pamatysime Kruskal algoritmo sudėtingumą, veikimą, pavyzdį ir įgyvendinimą.

Tačiau prieš pereidami tiesiai prie algoritmo, pirmiausia turėtume suprasti pagrindinius terminus, tokius kaip apimantis medis ir minimalus apimantis medis.

besitęsiantis medis - Apimamasis medis yra neorientuoto sujungto grafo pografas.

Mažiausias besitęsiantis medis – Minimalus apimantis medis gali būti apibrėžtas kaip apimantis medis, kuriame briaunos svorių suma yra minimali. Tvirtinimo medžio svoris yra svorių, pateiktų besitęsiančio medžio kraštams, suma.

Dabar pradėkime nuo pagrindinės temos.

Kruskal algoritmas naudojamas susieto svertinio grafiko minimaliam apimančiam medžiui rasti. Pagrindinis algoritmo tikslas yra rasti briaunų poaibį, kurį naudodami galėtume pereiti kiekvieną grafo viršūnę. Jame laikomasi godaus požiūrio, kuris kiekviename etape randa optimalų sprendimą, o ne sutelkia dėmesį į visuotinį optimalumą.

Kaip veikia Kruskal algoritmas?

Kruskal algoritme pradedame nuo mažiausio svorio kraštų ir toliau pridedame briaunas, kol pasiekiamas tikslas. Kruskal algoritmo įgyvendinimo veiksmai yra išvardyti taip:

• Pirmiausia surūšiuokite visus kraštus nuo mažo svorio iki didelio.
• Dabar paimkite mažiausio svorio kraštą ir pridėkite jį prie besitęsiančio medžio. Jei kraštas, kurį reikia pridėti, sukuria ciklą, tada atmeskite kraštą.
• Tęskite kraštų pridėjimą, kol pasieksime visas viršūnes ir bus sukurtas minimalus apimantis medis.

Kruskal algoritmo taikymas yra:

• Kruskal algoritmas gali būti naudojamas elektros instaliacijos išdėstymui tarp miestų.
• Jis gali būti naudojamas LAN jungtims nustatyti.

Kruskal algoritmo pavyzdys

Dabar pažiūrėkime, kaip veikia Kruskal algoritmas naudojant pavyzdį. Bus lengviau suprasti Kruskal algoritmą naudojant pavyzdį.

Tarkime, kad svertinis grafikas yra -

Aukščiau pateikto grafiko kraštų svoris pateiktas žemiau esančioje lentelėje -

Dabar surūšiuokite aukščiau pateiktus kraštus jų svorio didėjimo tvarka.

Dabar pradėkime statyti minimalų besitęsiantį medį.

len of masyvo java

1 žingsnis - Pirmiausia pridėkite kraštą AB su svoriu 1 į MST.

2 žingsnis - Pridėkite kraštą APIE su svoriu 2 į MST, nes ji nesukuria ciklo.

3 veiksmas – Pridėkite kraštą pr. Kr su svoriu 3 į MST, nes jis nesukuria jokio ciklo ar ciklo.

4 veiksmas – Dabar pasirinkite kraštą CD su svoriu 4 į MST, nes jis nesudaro ciklo.

5 veiksmas – Po to pasirinkite kraštą BET su svoriu 5. Įtraukus šį kraštą bus sukurtas ciklas, todėl jį išmeskite.

6 veiksmas - Pasirinkite kraštą AC su svoriu 7. Įtraukus šį kraštą bus sukurtas ciklas, todėl jį išmeskite.

7 veiksmas – Pasirinkite kraštą REKLAMA su svoriu 10. Įtraukus šį kraštą taip pat bus sukurtas ciklas, todėl jį išmeskite.

Taigi galutinis minimalus apimantis medis, gautas iš nurodyto svertinio grafiko, naudojant Kruskal algoritmą, yra -

MST kaina yra = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Dabar aukščiau pateikto medžio briaunų skaičius yra lygus viršūnių skaičiui atėmus 1. Taigi, algoritmas čia sustoja.

Algoritmas

 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 

Kruskal algoritmo sudėtingumas

Dabar pažiūrėkime, kiek laiko sudėtingas Kruskal algoritmas.

Laiko sudėtingumas
Kruskal algoritmo laiko sudėtingumas yra O(E logE) arba O(V logV), kur E yra Nr. briaunų, o V yra Nr. viršūnių.

Kruskal algoritmo įgyvendinimas

Dabar pažiūrėkime, kaip įgyvendinamas kruskal algoritmas.

Programa: Parašykite programą kruskalo algoritmui įgyvendinti C++ kalba.

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