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

Крускалын алгоритм (Анг. 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

Жишээ

Зураг	Тайлбар
	AD, CE хоёр нь хамгийн бага жинтэй ирмэгүүд буюу 5-ын жинтэй. Алийг нь ч сонгож болно. Энд AD-г сонголоо.
	CE нь дараагийн тойрог (цикл) үүсэхгүй хамгийн бага жинтэй ирмэг.
	Дараагийнх нь 6 жинтэй DF.
	Дараагийнх нь 7 жинтэй AB, BE хоёр. Алийг нь ч сонгож болно. AB-г сонголоо. Дараа нь BD-г улаанаар тэмдэглэсэн нь BD гэж холбовол ABD гэсэн тойрог үүсэх тул ийн тэмдэглэнэ.
	Дараагийн бага жинтэй ирмэг нь BE. BCE гэсэн тойрог үүсэх тул BC-г, DABE гэсэн тойрог үүсэх тул DE-г, FEBAD гэсэн тойрог үүсэх тул FE-г тус тус улаанаар тэмдэглэнэ.
	Дараагийн бага жинтэй ирмэг нь 9 жинтэй EG. Холболтын дараа ногооноор зурагдсан нь богино бүрхсэн мод гарсан байна.