logo

TechCodeview

Kruskala algoritms

Šajā rakstā mēs apspriedīsim Kruskal algoritmu. Šeit mēs redzēsim arī Kruskal algoritma sarežģītību, darbību, piemēru un ieviešanu.

Bet pirms virzīties tieši uz algoritmu, mums vispirms ir jāsaprot tādi pamatjēdzieni kā aptverošais koks un minimālais aptverošais koks.

aptverošs koks - Izvēršanas koks ir nevirzīta savienota grafika apakšgrafs.

Minimālais platuma koks - Minimālo stiepuma koku var definēt kā stiepuma koku, kurā malas svaru summa ir minimāla. Aptverošā koka svars ir to svaru summa, kas piešķirti stiepjošā koka malām.

Tagad sāksim ar galveno tēmu.

Kruskala algoritms tiek izmantots, lai atrastu savienotā svērtā grafika minimālo aptverošo koku. Algoritma galvenais mērķis ir atrast malu apakškopu, ar kuras palīdzību mēs varam šķērsot katru grafa virsotni. Tas seko mantkārīgai pieejai, kas katrā posmā atrod optimālu risinājumu, nevis koncentrējas uz globālo optimālo.

Kā darbojas Kruskal algoritms?

Kruskal algoritmā mēs sākam no malām ar mazāko svaru un turpinām pievienot malas, līdz tiek sasniegts mērķis. Kruskal algoritma ieviešanas soļi ir uzskaitīti šādi:

  • Vispirms sakārtojiet visas malas no maza svara uz augstu.
  • Tagad paņemiet malu ar mazāko svaru un pievienojiet to aptverošajam kokam. Ja pievienojamā mala izveido ciklu, tad malu noraidiet.
  • Turpiniet pievienot malas, līdz tiek sasniegtas visas virsotnes un tiek izveidots minimālais pārklājuma koks.

Kruskal algoritma pielietojumi ir -

  • Kruskal algoritmu var izmantot, lai izkārtotu elektrisko vadu starp pilsētām.
  • To var izmantot, lai izveidotu LAN savienojumus.

Kruškala algoritma piemērs

Tagad apskatīsim Kruskal algoritma darbību, izmantojot piemēru. Izmantojot piemēru, būs vieglāk saprast Kruskal algoritmu.

Pieņemsim, ka svērtais grafiks ir -

Kruskal

Iepriekš esošā grafika malu svars ir norādīts zemāk esošajā tabulā -

Mala AB AC AD BET BC CD OF
Svars 1 7 10 5 3 4 2

Tagad sakārtojiet iepriekš norādītās malas to svara augošā secībā.

Mala AB OF BC CD BET AC AD
Svars 1 2 3 4 5 7 10

Tagad sāksim konstruēt minimālo platuma koku.

ins atslēga

1. darbība — Vispirms pievienojiet malu AB ar svaru 1 uz MST.

Kruskal

2. darbība — Pievienojiet malu OF ar svaru 2 MST, jo tas nerada ciklu.

Kruskal

3. darbība — Pievienojiet malu BC ar svaru 3 uz MST, jo tas nerada nekādu ciklu vai cilpu.

Kruskal

4. darbība — Tagad izvēlieties malu CD ar svaru 4 uz MST, jo tas neveido ciklu.

Kruskal

5. darbība — Pēc tam izvēlieties malu BET ar svaru 5. Šīs malas iekļaušana radīs ciklu, tāpēc izmetiet to.

6. darbība — Izvēlieties malu AC ar svaru 7. Šīs malas iekļaušana radīs ciklu, tāpēc izmetiet to.

7. darbība — Izvēlieties malu AD ar svaru 10. Šīs malas iekļaušana arī izveidos ciklu, tāpēc izmetiet to.

Tātad galīgais minimālais aptverošais koks, kas iegūts no dotā svērtā grafika, izmantojot Kruskal algoritmu, ir -

Kruskal

MST izmaksas ir = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Tagad malu skaits iepriekš minētajā kokā ir vienāds ar virsotņu skaitu mīnus 1. Tātad algoritms šeit apstājas.

Algoritms

 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

Kruškāla algoritma sarežģītība

Tagad apskatīsim Kruskal algoritma laika sarežģītību.

    Laika sarežģītība
    Kruskala algoritma laika sarežģītība ir O(E logE) vai O(V logV), kur E ir nr. no malām, un V ir nr. no virsotnēm.

Kruškala algoritma realizācija

Tagad apskatīsim kruskal algoritma ieviešanu.

Programma: Uzrakstiet programmu kruskal algoritma ieviešanai C++ valodā.

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