Крускалын алгоритм

Крускалын алгоритм (Анг. Kruskal's Algorithm) нь графын онолд жинтэй графаас богино бүрхсэн мод (Анг. Minimum Spanning Tree) олох шуналтай алгоритм юм. Өөрөөр хэлбэл бүх оройг холбосон ирмэгүүд нь мод болох бөгөөд нийт ирмэгүүдийн жин нь хамгийн бага байх ёстой юм. Хэрэв богино бүрхсэн мод олдохгүй бол богино холбогдсон ой (Анг. minimum spanning forest) олдоно.

Энэхүү алгоритм анх 1956 онд Америкийн Математикийн Ертөнцийн Хөгжил (Анг. Proceedings of the American Mathematical Society) хэмээх сэтгүүлийн 48-50 дугаар хуудсанд Жосеф Крускалын нийтлэлд гарчээ.

Богино бүрхсэн мод олох бодлогыг мөн Примийн алгоритм, Хойноос нь устгах алгоритм, Борувкагийн алгоритм-уудаар боддог.

Тайлбар
 F хоосон ойг үүсгэнэ.
 Графын бүх ирмэгийг агуулсан S олонлогийг үүсгэнэ.
 S хоосон биш болон F богино холбогдсон мод болоогүй бол
 S-ээс хамгийн бага жинтэй ирмэгийг авна.
 F руу хийхэд ой болж байвал хийнэ.
 үгүй бол хаяна.

Алгоритмын төгсгөлд F-д богино бүрхсэн ой үүснэ. Хэрэв тэдгээр ойнууд нь хоорондоо холбогдсон бол нийтэд нь богино бүрхсэн мод гэнэ.

Псевдо код
 KRUSKAL(G):
 1 A = ∅
 2 foreach v ∈ G.V:
 3   MAKE-SET(v)
 4 foreach (u, v) ordered by weight(u, v), increasing:
 5    if FIND-SET(u) ≠ FIND-SET(v):
 6       A = A ∪ {(u, v)}
 7       UNION(u, v)
 8 return A
Жишээ
 Зураг  Тайлбар200pxAD, CE хоёр нь хамгийн бага жинтэй ирмэгүүд буюу 5-ын жинтэй. Алийг нь ч сонгож болно. Энд AD-г сонголоо.200pxCE нь дараагийн тойрог (цикл) үүсэхгүй хамгийн бага жинтэй ирмэг.200pxДараагийнх нь 6 жинтэй DF.200pxДараагийнх нь 7 жинтэй AB, BE хоёр. Алийг нь ч сонгож болно. AB-г сонголоо. Дараа нь BD-г улаанаар тэмдэглэсэн нь BD гэж холбовол ABD гэсэн тойрог үүсэх тул ийн тэмдэглэнэ.200pxДараагийн бага жинтэй ирмэг нь BE. BCE гэсэн тойрог үүсэх тул BC-г, DABE гэсэн тойрог үүсэх тул DE-г, FEBAD гэсэн тойрог үүсэх тул FE-г тус тус улаанаар тэмдэглэнэ.200pxДараагийн бага жинтэй ирмэг нь 9 жинтэй EG. Холболтын дараа ногооноор зурагдсан нь богино бүрхсэн мод гарсан байна. 

Ангилал:Алгоритм