Бүх нийтлэлүүд
2026.05.142 min read#алгоритмбаөгөгдлийнбүтэц#graph#tree#mst#prim#kruskal#algorithm
MST (Minimum Spanning Tree): Сүлжээний зардал хэмнэлтийн алгоритм
М.Хатанболд
Багш
М.Хатанболд
Багш
Инженерчлэл болон логистикийн салбарт аливаа системийг холбохдоо хамгийн бага зардал гаргах нь нэн тэргүүний зорилт байдаг. Үүнийг математик болон мэдээлэл зүйд Хамгийн бага жинтэй бүрхэгч мод (MST) гэх ойлголтоор шийддэг.
MST -ийг ойлгохын тулд бид эхлээд Граф гэж юу болохыг төсөөлөх хэрэгтэй. Граф бол ердөө хоорондоо холбогдсон цэгүүдийн систем юм.
Орой (Nodes): Холбогдох шаардлагатай объектууд (Жишээ нь: хотууд, компьютерууд).
Ирмэг (Edges): Тэдгээрийн хоорондох холбоос (Жишээ нь: зам, кабель).
Жин (Weight): Тухайн холбоосын зардал (Жишээ нь: замын урт, барилгын өртөг).
MST нь энэхүү граф дотроос бүх оройг холбосон, гэхдээ ирмэгүүдийнх нь жингийн нийлбэр хамгийн бага байх "дэд бүтэц"-ийг олох тухай асуудал юм.
MST байхын тулд дараах гурван нөхцөлийг заавал хангасан байна:
Бүх оройг хамарсан байх (Spanning): Нэг ч орой холбогдоогүй үлдэж болохгүй.
Цикл үүсгээгүй байх (Tree): Холбоосууд нь ямар нэгэн битүү зам буюу "тойрог" үүсгэж болохгүй. Хэрэв цикл үүсвэл тэр нь "илүүдэл" зардал болно.
Хамгийн бага зардалтай байх (Minimum): Боломжит бүх холболтын хувилбаруудаас хамгийн бага жинтэй нь байх ёстой.
MST алгоритмууд нь зардлыг хамгийн бага байлгах шаардлагатай бүхий л дэд бүтцийн асуудалд ашиглагддаг. Жишээ нь:
Сүлжээний холболт: Компьютеруудыг дотоод сүлжээнд холбохдоо кабелийн уртыг хамгийн бага байлгах.
Хотын төлөвлөлт: Хотуудын хооронд засмал зам, төмөр зам эсвэл дулаан болон бохирын хоолой татахдаа нийт зардлыг хэмнэх.
Цахилгаан түгээлт: Цахилгааны станцаас айл өрхүүд рүү утас татахдаа материалын зардлыг хамгийн бага түвшинд барих.
MST-ийг олох хамгийн алдартай хоёр арга бол Примийн алгоритм болон Крускалын алгоритм юм. Тэд хоёулаа "шунахай" (greedy) арга ашигладаг боловч ажиллах зарчим нь ялгаатай.
Крускалын алгоритм (Kruskal's Algorithm)
Энэ нь "Ирмэг төвтэй шунахай алгоритм" юм. Графын ирмэгүүдийг жингээр нь өсөх дарааллаар эрэмбэлж, хамгийн бага жинтэйгээс нь эхлэн цикл үүсгэхгүйгээр түүж авах зарчмаар ажилладаг.
Алхамчилсан заавар:
Графын бүх ирмэгийг жингийнх нь өсөх дарааллаар (хамгийн багаас их рүү) эрэмбэлж жагсаана.
Хамгийн бага жинтэй ирмэгийг жагсаалтаас сонгож авна.
Сонгосон ирмэгийг одоо байгаа MST-д нэмэхэд цикл (битүү зам) үүсэж байгаа эсэхийг шалгана.
Хэрэв цикл үүсэхгүй бол: Тухайн ирмэгийг MST-д нэмнэ.
Хэрэв цикл үүсвэл: Тухайн ирмэгийг орхиж, дараагийн ирмэг рүү шилжинэ.
Нийт ирмэгийн тоо V-1 (V нь оройн тоо) болох хүртэл 2-3 дугаар алхмыг давтана.
Зөвлөгөө: Цикл үүсэж буйг хурдан шалгахын тулд ихэвчлэн DSU (Disjoint Set Union) өгөгдлийн бүтцийг ашигладаг.
Примийн алгоритм (Prim's Algorithm)
Энэ нь "Орой төвтэй шунахай (Greedy) алгоритм" юм. Нэг дурын оройноос эхэлж, алхам тутамд тухайн "ургаж буй мод" -оос хамгийн ойр орших (хамгийн бага жинтэй ирмэгээр холбогдсон) шинэ оройг нэгтгэх зарчмаар ажилладаг.
Алхамчилсан заавар:
Графын аль нэг оройг дур мэдэн сонгож MST-д нэмнэ.
Одоогийн MST-д багтсан оройнуудыг, MST-д хараахан ороогүй байгаа оройнуудтай холбосон бүх ирмэгийг авч үзнэ.
Тэдгээр ирмэгүүдээс хамгийн бага жинтэйг нь сонгож, уг ирмэгийн нөгөө үзүүрт байгаа оройг MST-д нэмнэ.
Графын бүх орой MST-д орох хүртэл 2-3 дугаар алхмыг давтана.
Зөвлөгөө: Хамгийн бага жинтэй ирмэгийг хурдан олохын тулд Priority Queue ашигладаг.
Хэрэв та маш олон ирмэгтэй, бүх цэг нь хоорондоо холбогдох боломжтой сүлжээ дээр ажиллаж байвал Примийн алгоритм илүү хурдан. Харин ирмэгүүд нь цөөхөн, сийрэг сүлжээний хувьд Крускалын алгоритмыг ашиглах нь хэрэгжүүлэхэд илүү хялбар бөгөөд үр дүнтэй байдаг.