Крускал vs Прим
Компьютерийн шинжлэх ухаанд Прим ба Крускал алгоритмууд нь холбосон жигнэсэн чиглүүлээгүй графикийн хамгийн бага хүрээний модыг олдог шуналтай алгоритм юм. Графикийн зангилаа бүр нь мод болох замаар холбогдсон графын дэд хэсэг юм. Бүрхүүлтэй мод бүр өөрийн жинтэй бөгөөд бүх хүрээтэй модны боломжит хамгийн бага жин/зардал нь хамгийн бага хүрээтэй мод (MST) байна.
Примийн алгоритмын талаар дэлгэрэнгүй
Алгоритмыг 1930 онд Чехийн математикч Войтех Ярник, дараа нь 1957 онд компьютерийн эрдэмтэн Роберт С Прим бие даан боловсруулсан. 1959 онд Эдгер Дийкстра дахин нээсэн. Алгоритмыг гурван үндсэн үе шаттайгаар илэрхийлж болно;
Холбогдсон графикийг n зангилаа болон ирмэг бүрийн тус тусын жинг өгвөл
1. Графикаас дурын зангилаа сонгоод T модонд нэмнэ үү (энэ нь эхний зангилаа болно)
2. Модны зангилаатай холбогдсон ирмэг бүрийн жинг авч үзээд хамгийн бага хэмжээг сонгоно уу. T модны нөгөө үзүүрт ирмэг ба зангилааг нэмж графикаас ирмэгийг нь хас. (Хэрэв хоёр ба түүнээс дээш доод хэмжээ байгаа бол аль нэгийг нь сонгоно уу)
3. Модон дээр n-1 ирмэг нэмэгдэх хүртэл 2-р алхамыг давтана уу.
Энэ аргын хувьд мод нь нэг дурын зангилаанаас эхэлж, мөчлөг бүрээр тэр зангилаанаас цааш тэлэх болно. Тиймээс алгоритм зөв ажиллахын тулд график нь холбогдсон график байх ёстой. Примийн алгоритмын үндсэн хэлбэр нь O(V2). цагийн нарийн төвөгтэй байдалтай байна.
Крускалын алгоритмын талаар дэлгэрэнгүй
Жозеф Крускалын боловсруулсан алгоритм нь 1956 онд Америкийн Математикийн Нийгэмлэгийн үйл ажиллагаанд гарсан. Крускалын алгоритмыг мөн гурван энгийн алхамаар илэрхийлж болно.
n зангилаа, ирмэг тус бүрийн жин бүхий графикийг өгвөл
1. Графикаас хамгийн бага жинтэй нумыг сонгоод мод дээр нэмээд графикаас устгана уу.
2. Үлдсэн хэсгээс хамгийн бага жинтэй ирмэгийг цикл үүсгэхгүй байхаар сонгоно. Модны ирмэгийг нэмж, графикаас устгана уу. (Хэрэв хоёр ба түүнээс дээш доод хэмжээ байгаа бол аль нэгийг нь сонгоно уу)
3. 2-р алхам дээрх үйлдлийг давтана уу.
Энэ аргын хувьд алгоритм нь хамгийн бага жинтэй ирмэгээс эхэлж, мөчлөг бүр дээр ирмэг бүрийг үргэлжлүүлэн сонгоно. Тиймээс алгоритмд графикийг холбох шаардлагагүй. Крускал алгоритм нь цаг хугацааны нарийн төвөгтэй O(logV)
Крускал болон Прим алгоритмын ялгаа нь юу вэ?
• Примийн алгоритм нь зангилаагаар эхэлдэг бол Крускалийн алгоритм нь ирмэгээр эхэлдэг.
• Примийн алгоритмууд нэг зангилаанаас нөгөөд дамждаг бол Крускал алгоритм нь ирмэгийн байрлалыг сүүлчийн алхам дээр тулгуурлаагүй байдлаар ирмэгийг сонгодог.
• Примийн алгоритмд график нь холбогдсон график байх ёстой, харин Крускал нь салгагдсан график дээр мөн ажиллах боломжтой.
• Примийн алгоритм нь O(V2) цагийн нарийн төвөгтэй, Крускалын цаг хугацааны нарийн төвөгтэй байдал нь O(logV).
