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

Чөлөөт нэвтэрхий толь, Википедиагаас
Харайх: Удирдах, Хайлт

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

Жишээ[засварлах]

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