Kruskal vs Prim
Kompüter elmində Prim və Kruskal alqoritmləri əlaqəli çəkili istiqamətsiz qrafik üçün minimum əhatəli ağac tapan acgöz alqoritmdir. Genişlənmiş ağac qrafikin alt qrafasıdır ki, qrafikin hər bir qovşağı ağac olan bir yol ilə bağlanır. Hər bir uzanan ağacın çəkisi var və bütün uzanan ağacların minimum mümkün çəkisi/qiyməti minimum yayılma ağacıdır (MST).
Prim alqoritmi haqqında ətraflı
Alqoritm 1930-cu ildə çex riyaziyyatçısı Voytěch Jarník və daha sonra müstəqil olaraq 1957-ci ildə kompüter alimi Robert C. Prim tərəfindən hazırlanmışdır. O, 1959-cu ildə Edsger Dijkstra tərəfindən yenidən kəşf edilmişdir. Alqoritmi üç əsas addımda ifadə etmək olar;
N qovşaq və hər kənarın müvafiq çəkisi ilə əlaqəli qrafiki nəzərə alaraq, 1. Qrafikdən ixtiyari qovşaq seçin və onu T ağacına əlavə edin (bu, ilk qovşaq olacaq)
2. Ağacdakı qovşaqlara qoşulmuş hər bir kənarın çəkilərini nəzərə alın və minimumu seçin. T ağacının digər ucundakı kənarı və düyünü əlavə edin və kənarı qrafikdən çıxarın. (İki və ya daha çox minimum varsa, hər hansı birini seçin)
3. n-1 kənarları ağaca əlavə olunana qədər 2-ci addımı təkrarlayın.
Bu üsulda ağac tək ixtiyari düyünlə başlayır və hər dövrə ilə həmin qovşaqdan genişlənir. Beləliklə, alqoritmin düzgün işləməsi üçün qrafikin əlaqəli qrafik olması lazımdır. Prim alqoritminin əsas forması O(V2) zaman mürəkkəbliyinə malikdir.
Kruskal alqoritmi haqqında ətraflı
Cozef Kruskal tərəfindən hazırlanmış alqoritm 1956-cı ildə Amerika Riyaziyyat Cəmiyyətinin araşdırmalarında ortaya çıxdı. Kruskalın alqoritmini üç sadə addımda da ifadə etmək olar.
N qovşaq və hər kənarın müvafiq çəkisi olan qrafiki nəzərə alaraq, 1. Bütün qrafikin ən az çəkisi olan qövsü seçin və ağaca əlavə edin və qrafikdən silin.
2. Qalanlardan ən az çəkilmiş kənarı, dövrə yaratmayacaq şəkildə seçin. Ağacın kənarını əlavə edin və qrafikdən silin. (İki və ya daha çox minimum varsa, hər hansı birini seçin)
3. 2-ci addımdakı prosesi təkrarlayın.
Bu üsulda alqoritm ən az çəkili kənardan başlayır və hər dövrədə hər kənarı seçməyə davam edir. Buna görə də, alqoritmdə qrafiki birləşdirməyə ehtiyac yoxdur. Kruskalın alqoritmi O(logV) zaman mürəkkəbliyinə malikdir
Kruskal və Prim alqoritmi arasında fərq nədir?
• Primin alqoritmi qovşaqla, Kruskalın alqoritmi isə kənar ilə başlayır.
• Primin alqoritmləri bir qovşaqdan digərinə yayılır, Kruskalın alqoritmi isə kənarları elə seçir ki, kənarın mövqeyi son addıma əsaslanmır.
• Prim alqoritmində qrafik əlaqəli qrafik olmalıdır, Kruskal isə əlaqəsi kəsilmiş qrafiklərdə də işləyə bilər.
• Primin alqoritminin zaman mürəkkəbliyi O(V2) və Kruskalın zaman mürəkkəbliyi O(logV).
