Diferența dintre Kruskal și Prim

Kruskal vs Prim

În domeniul informaticii, algoritmii lui Prim și Kruskal sunt un algoritm lacom care găsește un copac minim pentru un grafic nedirecționat ponderat. Un copac spanning este un subgraf al unui grafic astfel încât fiecare nod al graficului este conectat printr-o cale, care este un copac. Fiecare arbore spanning are o greutate, iar greutatea minimă posibilă / costul tuturor arborilor care se întind, este arborele minim de întindere (MST).

Mai multe despre algoritmul lui Prim

Algoritmul a fost dezvoltat de matematicianul ceh Vojtěch Jarník în 1930 și ulterior independent de omul de știință Robert C. Prim în 1957. El a fost redescoperit de Edsger Dijkstra în 1959. Algoritmul poate fi declarat în trei pași cheie;

Având în vedere graficul conectat cu n noduri și greutatea fiecărei margini,

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 muchii conectate la nodurile din arbore și selectați minimul. Adăugați marginea și nodul la celălalt capăt al arborelui T și scoateți marginea din grafic. (Selectați dacă există două sau mai multe minime)

3. Repetați pasul 2, până când n-1 marginile sunt adăugate copacului.

În această metodă, arborele începe cu un singur nod arbitrar și se extinde de la acel nod către fiecare ciclu. Prin urmare, pentru ca algoritmul să funcționeze corect, graficul trebuie să fie un grafic conectat. Forma de bază a algoritmului Prim are o complexitate de timp a lui O (V²).

Mai multe despre algoritmul lui Kruskal

Algoritmul dezvoltat de Joseph Kruskal a apărut în cadrul lucrărilor Societății Americane de Matematică din 1956. Algoritmul lui Kruskal poate fi exprimat și în trei pași simpli.

Având în vedere graficul cu n noduri și greutatea fiecărei margini,

1. Selectați arcul cu cea mai mică greutate a întregului grafic și adăugați-l în copac și ștergeți-l din grafic.

2. Din restul selectați marginea cea mai puțin ponderată, într-un mod care nu formează un ciclu. Adăugați marginea copacului și ștergeți-o din grafic. (Selectați dacă există două sau mai multe minime)

3. Repetați procesul la pasul 2.

În această metodă, algoritmul începe cu marginea cea 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 de timp a lui 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 lui prim, graficul trebuie să fie un grafic conectat în timp ce Kruskal poate funcționa și pe grafice deconectate.

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