Diferența Dintre Kruskal și Prim

2024 Autor: Mildred Bawerman | [email protected]. Modificat ultima dată: 2023-12-16 08:41

Kruskal vs Prim

În informatică, algoritmii lui Prim și Kruskal sunt un algoritm lacom care găsește un copac minim care se întinde pentru un grafic conectat nedirectat. Un copac întins este un subgraf al unui grafic astfel încât fiecare nod al graficului este conectat printr-o cale, care este un copac. Fiecare copac care se întinde are o greutate, iar greutatea minimă posibilă / costul tuturor copacilor care se întind este arborele minim care se întinde (MST).

Mai multe despre algoritmul lui Prim

Algoritmul a fost dezvoltat de matematicianul ceh Vojtěch Jarník în 1930 și ulterior independent de informaticianul Robert C. Prim în 1957. A fost redescoperit de Edsger Dijkstra în 1959. Algoritmul poate fi afirmat î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 copac și selectați minimul. Adăugați marginea și nodul de la celălalt capăt al arborelui T și îndepărtați marginea 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 la copac.

În această metodă, arborele începe cu un singur nod arbitrar și se extinde de la acel nod înainte 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 (V ²).

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 exprimat și în trei pași simpli.

Dat fiind graficul cu n noduri și greutatea respectivă 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-l din grafic.

2. Din restul selectați marginea cel mai puțin ponderată, într-un mod care să nu formeze un ciclu. Adăugați marginea în copac ș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 cel mai puțin ponderată și continuă să selecteze fiecare margine la fiecare ciclu. Prin urmare, în algoritm graficul nu trebuie conectat. Algoritmul lui Kruskal are o complexitate temporală de O (logV)

Care este diferența dintre algoritmul lui Kruskal și Prim?

• Algoritmul lui Prim 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ă marginile astfel încât poziția marginii să nu se bazeze pe ultimul pas.

• În algoritmul prim, graficul trebuie să fie un grafic conectat, în timp ce Kruskal poate funcționa și pe graficele deconectate.

• Algoritmul lui Prim are o complexitate temporală de O (V ²), iar complexitatea de timp a lui Kruskal este O (logV).