Graph : Энэ ч граф тэр ч граф !!!

Энгүүнбаяр Ганзориг

• 2025-05-31

Энэ удаа бид DSA-н хамгийн “үнэнч найз” болох Graph буюу Графын өгөгдлийн бүтэц-ийн тухай жинхэнэ утгаар нь ойлгож авцгаая. Найз нөхдийн харилцаа, замын сүлжээ, интернет холболт гээд бидний амьдралын бараг бүх л систем граф дээр суурилдаг. Тийм болохоор “энэ ч граф, тэр ч граф” гэхэд бараг буруудахгүй ээ .

Graph гэж юу вэ?

Graph нь объектууд (өнцөг) болон тэдгээрийн хоорондох харилцаа (холбоосууд)-ыг дүрсэлдэг өгөгдлийн бүтэц юм.

• Өнцөг (Vertex): Нэгж объект. Жишээ нь: хот, хүн, сервер.
• Холбоос (Edge): Оргилуудын хоорондын холбоо. Жишээ нь: зам, найзын хүсэлт, кабель.

Бодитоор төсөөлөхөд:

• Facebook → Хүмүүс = Оргилууд, Найзын холбоо = Холбоос
• Google Maps → Хот = Оргил, Зам = Холбоос
• Вэб хуудас → Хуудас = Оргил, Холбоос = Линк

Графын төрлүүд

1. Чиглэлтэй (Directed Graph) – Холбоос нь нэг чиглэлтэй.
   • A → B, гэхдээ B → A биш байж болно.
   • Жишээ: Instagram-ийн бие биенээ дагадаг шиг логик
2. Чиглэлгүй (Undirected Graph) – Холбоос хоёр чиглэлд нээлттэй.
   • A — B гэвэл хоёр талдаа нөлөөтэй.
   • Жишээ: Facebook найзын систем
3. Жинтэй (Weighted Graph) – Холбоос бүр жинтэй буюу “үнэтэй”.
   • Жишээ: Хотын хоорондын зай, өгөгдөл дамжуулах хурд
4. Мод (Tree) – Нэгэн төрлийн граф. Цагираггүй ба холбоотой.
   • Ямар ч 2 оргилын хооронд ганц зам л байдаг.
   • Жишээ: File системийн бүтэц
5. Цагирагтай/Цагираггүй (Cyclic/Acyclic) – Зарим граф дотроо буцаж өөртөө хүрч болдог.

Ямар алгоритмууд граф дээр ажилладаг вэ?

Түгээмэл андуурал, алдаа

• DFS/BFS-ийг хооронд нь андуурах (анхаар: BFS → түвшин, DFS → гүн)
• Жинтэй граф дээр BFS ашиглах — Буруу! → Dijkstra эсвэл Bellman-Ford
• Цагираг шалгаагүйгээс recursion stack overflow
• Disconnected components буюу салангид хэсгүүдийг хайж чадахгүй байх

Graph яагаад чухал вэ?

• Competitive Programming дээр ~30% нь графтай холбоотой
• AI, ML-ийн мэдлэгийн граф, semantic web
• Web crawling, social network analysis, dependency resolution гээд л хязгааргүй хэрэглээтэй

Дүгнэлт

Graph бол DSA-н хамгийн “амьд” өгөгдлийн бүтэц. Амьдралын бараг бүх асуудлыг түүгээр загварчилж болдог. Гэхдээ анхаараарай , алгоритм бүр тохирох нөхцөлтэй, тиймээс graph-ийн төрлийг таних чадвар бол үнэтэй зэвсэг юм.

Дараагийн нийтлэл: “DFS vs BFS: Гүн чухал уу ? , Өргөн чухал уу ?”
Удахгүй уулзъя! Graph you later!