Muchii în arbore
Lungime totală
Muchii verificate

  • Curent
  • În arbore
  • Ar închide un ciclu

Mai multe despre algoritmul lui Kruskal

Algoritmul lui Kruskal

Algoritmul lui Kruskal construiește un arbore parțial de cost minim, cel mai ieftin set de muchii care leagă toate nodurile, în cel mai simplu mod imaginabil: luați muchiile de la cea mai scurtă la cea mai lungă și păstrați-o pe fiecare, dacă nu închide un ciclu. Avansați pas cu pas ca să vedeți cum părți separate cresc și se unesc într-un singur arbore, precum și muchiile sărite. Apăsați Redare pentru a urmări cum crește arborele sau folosiți Pas și Înapoi pentru a avansa câte un pas. Trageți glisorul pentru pași pentru a sări oriunde. Numărul de pe fiecare muchie este lungimea ei. Sub graf sunt muchiile rămase de încercat, de la cea mai scurtă la cea mai lungă; o muchie ale cărei capete sunt deja legate ar închide un ciclu și este trasată cu linie întreruptă roșie. Graf nou creează alt graf; alegeți câte noduri și muchii are. Cu tabla selectată, tastele săgeți avansează pas cu pas, bara de spațiu pornește și oprește redarea, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Apăsați Redare sau folosiți Pas și Înapoi pentru a avansa câte un pas.
  2. Trageți glisorul pentru pași pentru a sări oriunde. Muchiile rămase de încercat sunt listate sub graf, de la cea mai scurtă.
  3. Urmăriți muchiile trasate cu linie întreruptă roșie: ar închide un ciclu. Graf nou creează alt graf de încercat.

Cum funcționează algoritmul lui Kruskal

Sortați toate muchiile de la cea mai scurtă la cea mai lungă. Începeți cu fiecare nod ca parte separată. Încercați muchiile în ordine: dacă o muchie unește două părți diferite, intră în arbore, iar cele două părți devin una; dacă ambele capete sunt deja în aceeași parte, ar închide un ciclu, deci săriți peste ea. Opriți-vă când totul este o singură parte. Asta se întâmplă după cu o muchie mai puțin decât numărul de noduri, adesea cu mult înainte de a încerca ultima muchie.

Union-find

Pentru fiecare muchie, algoritmul lui Kruskal trebuie să întrebe dacă cele două capete ale ei sunt deja legate. O structură union-find răspunde repede: fiecare parte are un singur reprezentant, find urmează legăturile până la el, iar union leagă un reprezentant de celălalt. Cu două trucuri simple, comprimarea drumului și uniunea după mărime, fiecare întrebare durează un timp aproape constant, deci sortarea muchiilor este partea cea mai lentă, cu un efort care crește cu E log E.

Întrebări frecvente

Ce este algoritmul lui Kruskal?

Un algoritm greedy care construiește un arbore parțial de cost minim sortând toate muchiile de la cea mai scurtă la cea mai lungă și adăugând fiecare muchie care nu închide un ciclu cu muchiile deja alese.

Cum detectează algoritmul lui Kruskal un ciclu?

O muchie închide un ciclu exact atunci când cele două capete ale ei sunt deja legate prin muchii alese. O structură union-find ține evidența nodurilor legate și răspunde la această întrebare aproape instantaneu.

De ce funcționează algoritmul lui Kruskal?

Datorită proprietății ciclului: cea mai lungă muchie de pe orice ciclu nu este niciodată necesară pentru un arbore parțial de cost minim. Fiecare muchie sărită de Kruskal este cea mai lungă de pe ciclul pe care l-ar închide, pentru că toate muchiile dinaintea ei erau mai scurte sau egale.

Când să folosesc Kruskal în loc de Prim?

Algoritmul lui Kruskal este simplu și rapid pe grafuri rare și lucrează direct pe o simplă listă de muchii. Algoritmul lui Prim se potrivește grafurilor dense și celor memorate ca liste de adiacență. Amândoi găsesc un arbore cu aceeași lungime totală.

Este graful meu trimis undeva?

Nu. Graful este creat și arborele este construit în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor