Când ar trebui să folosesc Kruskal în loc de Prim (și invers)? (Programare, Algoritm, Teoria Grafurilor, Arborele Minim De Cuprindere, Algoritmul Prims, Algoritmul Kruskals)

ebe a intrebat.

Mă întrebam când ar trebui să se folosească algoritmul lui Prim și când Kruskal pentru a găsi arborele minim de cuprindere? Ambele au o logică ușoară, aceleași cazuri cele mai grave și singura diferență este implementarea care ar putea implica structuri de date puțin diferite. Deci, care este factorul decisiv?

10 răspunsuri
Todd Gamblin

Utilizați algoritmul lui Prim atunci când aveți un graf cu multe muchii.

Pentru un graf cu V vârfuri E muchii, algoritmul lui Kruskal se execută în O(E log V) timp, iar algoritmul lui Prim poate rula în O(E + V log V) în timp amortizat, dacă se utilizează un grămadă Fibonacci Heap.

Algoritmul lui Prim este semnificativ mai rapid la limită atunci când aveți un graf foarte dens, cu mult mai multe muchii decât vârfuri. Kruskal se comportă mai bine în situații tipice (grafuri rare) deoarece utilizează structuri de date mai simple.

Comentarii

  • Aș spune „situații tipice” în loc de medii… Cred că este un termen obscur de utilizat, de exemplu, care este „dimensiunea medie” a unui tabel hash? habar nu am. –  > Por yairchu.
  • @SplittingField: Eu cred că tu chiar compari mere și portocale. Analiza amortizată este pur și simplu o modalitate de a obține o măsură a funcției (ca să spunem așa) — dacă este cel mai rău caz sau cazul mediu depinde de ceea ce dovedești. De fapt (după cum mă uit acum), articolul din wiki folosește un limbaj care implică faptul că doar utilizat pentru analiza celui mai rău caz. Acum, utilizarea unei astfel de analize înseamnă că nu se pot face promisiuni la fel de puternice cu privire la costul unei anumite operații, dar în momentul în care algoritmul este gata, acesta va fi într-adevăr de O(E+VlogV), chiar și în cel mai rău caz. –  > Por agorenst.
  • Asta sună bine în teorie, dar pun pariu că puțini oameni pot implementa un heap Fibonacci –  > Por Alexandru.
  • @tgamblin, pot exista C(V,2) muchii în cel mai rău caz. Deci, nu cumva complezența în timp a algoritmului lui Prim se reduce la O(V^2 + VlogV) adică O(V^2) în cazul unui heap Fibonacci? –  > Por Spiridușul verde.
  • Mai există un alt factor important: ieșirea lui Prims este un MST doar dacă graful este conex (ieșirea mi se pare inutilă în caz contrar), dar ieșirea lui Kruskal este Minimum Spanning forests (cu oarecare utilitate). –  > Por Andrei I.
Snicolas

Am găsit pe net un thread foarte frumos care explică diferența într-un mod foarte simplu : http://www.thestudentroom.co.uk/showthread.php?t=232168.

Algoritmul lui Kruskal va crește o soluție pornind de la cea mai ieftină muchie prin adăugarea următoarei muchii mai ieftine, cu condiția să nu creeze un ciclu.

Algoritmul lui Prim va dezvolta o soluție pornind de la un vertex aleatoriu prin adăugarea următorului cel mai ieftin vertex, vertexul care nu se află în prezent în soluție, dar care este conectat la aceasta prin cea mai ieftină muchie.

Aici atașat este o fișă interesantă pe această temă.

Dacă implementați atât Kruskal, cât și Prim, în forma lor optimă: cu un union find și, respectiv, un finbonacci heap, veți observa cum Kruskal este ușor de implementat în comparație cu Prim.

Prim este mai dificil cu un heap fibonacci în principal pentru că trebuie să mențineți un tabel de evidență pentru a înregistra legătura bidirecțională dintre nodurile grafului și nodurile heap. Cu un Union Find, este invers, structura este simplă și poate chiar produce direct mst-ul aproape fără costuri suplimentare.

Comentarii

  • Nitpick: Ultimul „diapozitiv” din fiecare ar trebui să se citească „repeat until you have a spanning tree”; nu până la MST, care este un fel de sarcină recursivă – de unde să știu că este minimă – de aceea o urmez pe cea a lui Prim/Kruskal pentru început! –  > Por OJFord.
  • @OllieFord Am găsit acest fir pentru că am căutat o ilustrare simplă a algoritmilor Prim și Kruskal. Algoritmii garantează că veți găsi un arbore și că acel arbore este un MST. Și știi că ai găsit un arbore atunci când ai exact V-1 muchii. –  > Por mikedu95.
  • @mikedu95 Ai dreptate, faci același lucru ca și comentariul meu anterior dintr-un unghi diferit. –  > Por OJFord.
  • Dar nu este o precondiție faptul că trebuie să alegi doar cu o singură greutate între vârfuri, nu poți alege greutatea 2 de mai multe ori din graficul de mai sus, trebuie să alegi următoarea greutate ex:3 @Snicolas -.  > Por ani0904071.
malejpavouk

Știu că nu ați cerut acest lucru, dar dacă aveți mai multe unități de procesare, ar trebui să luați întotdeauna în considerare Algoritmul lui Borůvka, , deoarece ar putea fi ușor de paralelizat – prin urmare, are un avantaj de performanță față de algoritmul Kruskal și Jarník-Prim.

Daniel C. Sobral

Kruskal poate avea performanțe mai bune dacă marginile pot fi sortate în timp liniar sau dacă sunt deja sortate.

Prim este mai bun dacă numărul de muchii către vârfuri este mare.

Ghiurutan Alexandru

Kruskal complexitatea în timp în cel mai rău caz este O(E log E),aceasta deoarece trebuie să sortăm marginile. Prim complexitatea timpului în cel mai rău caz este O(E log V) cu coadă de prioritate sau chiar mai bine, O(E+V log V) cu grămada Fibonacci. Ar trebui să folosim Kruskal atunci când graful este rarefiat, adică un număr mic de muchii, cum ar fi E=O(V), când muchii sunt deja sortate sau dacă le putem sorta în timp liniar. Ar trebui să folosim Prim atunci când graful este dens, adică numărul de muchii este mare, cum ar fi E=O(V²).

Comentarii

  • Mi se pare că Prim nu este niciodată mai rău decât Kruskal în ceea ce privește viteza. Deoarece E ar trebui să fie cel puțin V-1 dacă există un arbore de cuprindere. Cred că motivul pentru care putem prefera Kruskal pentru un graf rar este că structura sa de date este foarte simplă. –  > Por Yu Gu.
Prakhar

Dacă oprim algoritmul la mijloc, algoritmul lui Prim generează întotdeauna un arbore conectat, dar Kruskal, pe de altă parte, poate da un arbore deconectat sau o pădure.

Jaskaran

O aplicație importantă a algoritmului lui Kruskal este în gruparea pe o singură legătură.

Luați în considerare n vârfuri și aveți un graf complet.Pentru a obține un grup de k clustere din acele n puncte.rulați algoritmul lui Kruskal peste primele n-(k-1) muchii din setul de muchii sortate.obțineți un grup de k clustere ale grafului cu spațiere maximă.

Leon Stenneth

Cel mai bun timp pentru Kruskal’s este O(E logV). Pentru Prim’s folosind fib heaps se poate obține O(E+V lgV). Prin urmare, pe un graf dens, Prim’s este mult mai bun.

Sakshi

Prim’s este mai bun pentru grafurile mai dense și, de asemenea, nu trebuie să acordăm prea multă atenție ciclurilor prin adăugarea unei muchii, deoarece avem de-a face în primul rând cu noduri. Prim’s este mai rapid decât Kruskal’s în cazul grafurilor complexe.

Abhishek

În algoritmul Kruskal, avem numărul de muchii și numărul de vârfuri pe un graf dat, dar pe fiecare muchie avem o anumită valoare sau greutate în numele căreia putem pregăti un nou graf care trebuie să nu fie ciclic sau să nu fie apropiat din nicio parte.

un graf ca acesta: _____________ | | | | | | | | | |__________ | |Dați un nume oricărui vârf a,b,c,d,e,f .