Kruskal vs Prim
În informatică, algoritmii lui Prim și Kruskal sunt un algoritm lacom care găsește un arbore de acoperire minim pentru un grafic nedirecționat ponderat conectat. Un arbore de întindere este un subgraf al unui grafic astfel încât fiecare nod al graficului este conectat printr-o cale, care este un arbore. Fiecare arbore de întindere are o greutate, iar greutatea/costul minim posibil al tuturor arborilor de întindere este arborele de întindere minim (MST).
Mai multe despre algoritmul lui Prim
Algoritmul a fost dezvoltat de matematicianul ceh Vojtěch Jarník în 1930 și mai târziu independent de informaticianul Robert C. Prim în 1957. A fost redescoperit de Edsger Dijkstra în 1959. Algoritmul poate fi formulat în trei pași cheie;
Având în vedere graficul conectat cu n noduri și greutatea respectivă a fiecărei muchii, 1. Selectați un nod arbitrar din grafic și adăugați-l în arborele T (care va fi primul nod)
2. Luați în considerare greutățile fiecărei margini conectate la nodurile din arbore și selectați minimul. Adăugați muchia și nodul de la celăl alt capăt al arborelui T și eliminați muchia din grafic. (Selectați oricare dacă există două sau mai multe minime)
3. Repetați pasul 2, până când n-1 margini sunt adăugate în arbore.
În această metodă, arborele începe cu un singur nod arbitrar și se extinde de la acel nod în continuare cu fiecare ciclu. Prin urmare, pentru ca algoritmul să funcționeze corect, graficul trebuie să fie un grafic conectat. Forma de bază a algoritmului lui Prim are o complexitate temporală de O(V2).
Mai multe despre algoritmul lui Kruskal
Algoritmul dezvoltat de Joseph Kruskal a apărut în lucrările Societății Americane de Matematică în 1956. Algoritmul lui Kruskal poate fi, de asemenea, exprimat în trei pași simpli.
Având în vedere graficul cu n noduri și greutatea corespunzătoare a fiecărei muchii, 1. Selectați arcul cu cea mai mică greutate din întregul grafic și adăugați-l în arbore și ștergeți din grafic.
2. Dintre restul selectați marginea cel mai puțin ponderată, într-un mod care să nu formeze un ciclu. Adăugați marginea în arbore și ștergeți din grafic. (Selectați oricare dacă există două sau mai multe minime)
3. Repetați procesul de la pasul 2.
În această metodă, algoritmul începe cu marginea cea mai mică ponderată și continuă să selecteze fiecare margine la fiecare ciclu. Prin urmare, în algoritm, graficul nu trebuie să fie conectat. Algoritmul lui Kruskal are o complexitate de timp de O(logV)
Care este diferența dintre algoritmul lui Kruskal și cel al lui Prim?
• Algoritmul lui Prim se inițializează cu un nod, în timp ce algoritmul lui Kruskal inițiază cu o margine.
• Algoritmii lui Prim se întind de la un nod la altul, în timp ce algoritmul lui Kruskal selectează muchiile astfel încât poziția muchiei să nu se bazeze pe ultimul pas.
• În algoritmul lui prim, graficul trebuie să fie un grafic conectat, în timp ce Kruskal-ul poate funcționa și pe grafice deconectate.
• Algoritmul lui Prim are o complexitate de timp de O(V2), iar complexitatea de timp a lui Kruskal este O(logV).
