Qo'shnilik(qo'shni tugunlar) ro'yxati – bu A[n] massiv bo'lib, A[i] har bir elementi i tugun bilan qo'shni tugunlar ro'yxatini o'zida saqlaydi.
Qo'shnilik(qo'shni tugunlar) ro'yxati qulaylik tomonlari quyidagilarda:
Joriy (berilgan) tugunga qo’shni tugunni izlash;
Tugun yoki qirra(yoy)larni qushish;
Siyrak graflar bilan ishlash.
Qo'shnilik(qo'shni tugunlar) ro'yxati noqulayliklari esa quyidagicha:
Qirra(yoy)ning mavjudligini tekshirish;
Tugun yoki qirra(yoy)larni o’chirish.
Qirralar ro'yxati – qirralarning qo'shni tugunlar juftliklaridan iborat chiziqli ro'yxatdir.
Qo'shnilik(qo'shni tugunlar) ro'yxati qulaylik tomonlari quyidagilarda:
Qirra(yoy)larni qushish yoki o’chirish;
Yoylarning yuklanishi bo’yicha tartiblash;
Siyrak graflar bilan ishlash.
Qo'shnilik(qo'shni tugunlar) ro'yxati noqulayliklari esa quyidagicha:
Tugun va qirra(yoy)ning qo’shniligini aniqlash;
Berilgan tugunga intsidient qirra(yoy)larni tanlash.
Graflarda ko'rik o'tkazish
Grafni ko'rikdan o'tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni bir martadan ko'rib chiqish amalidir.
Ko’rikdan o’tkazish ikkita usuli mavjud:
Chuqurligiga (tubiga) qarab qidirish (Depth-First Search – DFS)
Kengligiga (eniga) qarab qidirish (Breadth-First Search – BFS)
Bu usullar berilgan X tugundan boshlab bironta konteynerni qo'llagan holda barcha tugunlarni ko'rib chiqadi.
Chuqurlikka qarab ko'rishda stek tuzilmasi qo'llaniladi.
Kenglikka qarab ko'rishda esa navbat tuzilmasidan foydalaniladi.
Tubiga qarab ko’rikni o’tqazish psevdokodi quyidagicha amalga oshiriladi
A tugundan boshlab tubiga qarab ko’rib chiqish misoli
Eniga qarab ko’rikni o’tqazish psevdokodi quyidagicha amalga oshiriladi
A tugundan boshlab eniga qarab ko’rib chiqish misoli
Binar daraxtlarni qurish
Binar daraxtda har bir tugun-elementdan ko’pi bilan 2 ta shox chiqadi. Daraxtlarni xotirada tasvirlashda uning ildizini ko’rsatuvchi ko’rsatkich berilishi kerak. Daraxtlarni kompyuter xotirasida tasvirlanishiga ko’ra har bir element (binar daraxt tuguni) to’rtta maydonga ega yozuv shaklida bo’ladi, ya’ni kalit maydon, informatsion maydon, ushbu elementni o’ngida va chapida joylashgan elementlarning xotiradagi adreslari saqlanadigan maydonlar.
Shuni esda tutish lozimki, daraxt hosil qilinayotganda, otaga nisbatan chap tomondagi o’g’il qiymati kichik kalitga, o’ng tomondagi o’g’il esa katta qiymatli kalitga ega bo’ladi. Har safar daraxtga yangi element kelib qo’shilayotganda u avvalambor daraxt ildizi bilan solishtiriladi. Agar element ildiz kalit qiymatidan kichik bo’lsa, uning chap shoxiga, aks holda o’ng shoxiga o’tiladi. Agar o’tib ketilgan shoxda tugun mavjud bo’lsa, ushbu tugun bilan ham solishtirish amalga oshiriladi, aks holda, ya’ni u shoxda tugun mavjud bo’lmasa, bu element shu tugunga joylashtiriladi.
Masalan, daraxt tugunlari quyidagi qiymatlarga ega 6, 21, 48, 49, 52, 86, 101.
U holda binar daraxt ko’rinishi quyidagi 4.1-rasmdagidek bo’ladi:
4.1-rasm. Binar daraxt ko’rinishi
Natijada, o’ng va chap qism daraxtlari bir xil bosqichli tartiblangan binar daraxt hosil qildik. Agar daraxtning o’ng va chap qism daraxtlari bosqichlarining farqi birdan kichik bo’lsa, bunday daraxt ideal muvozanatlangan daraxt deyiladi. Yuqorida hosil qilgan binar daraxtimiz ideal muvozanatlangan daraxtga misol
bo’ladi. Daraxtni muvozanatlash algoritmini sal keyinroq ko’rib chiqamiz. Undan oldin binar daraxtni yaratish algoritmini o’rganamiz.
Dasturlarda dinamik ma’lumotlar tuzilmasidan ko’pincha chiziqli ro’yhatlar, steklar, navbatlar va binar daraxtlar ishlatiladi. Bu tuzilmalar bir-biridan elementlarning bog’lanish usuli va ular ustida bajarilishi mumkin bo’lgan amallari bilan farqlanadi. Dinamik tuzilmalar massiv va yozuvdan farqli ravishda operativ xotirada ketma-ket sohalarda joylashmaydi. Ixtiyoriy dinamik tuzilma elementi 2 ta maydondan tashkil topadi: tuzilma tashkil etilishiga sabab bo’layotgan informatsion maydon va elementlarning o’zaro aloqasini ta’minlovchi ko‘rsatkichli maydon. Chiziqli ro’yhatlarda har bir element o’zidan keyingisi yoki oldingisi bilan ham bog’langan bo’lishi mumkin. Birinchi holatda, ya’ni elementlar o’zidan keyingi element bilan bog’langan bo’lsa, bunday ro’yhatga bir bog‘lamli ro‘yhat deyiladi. Agar har bir element o’zidan oldingi va o’zidan keyingi element bilan bog’langan bo’lsa, u holda bunday ro’yhatlarga 2 bog‘lamli ro‘yhatlar deyiladi. Agar oxirgi element birinchi element ko’rsatkichi bilan bog’langan bo’lsa, bunday ro’yhatga halqasimon ro‘yhat deyiladi. Ro’yhatning har bir elementi shu elementni identifikatsiyalash uchun kalitga ega bo’ladi. Kalit odatda butun son yoki satr ko’rinishida ma’lumotlar maydonining bir qismi sifatida mavjud bo’ladi. Ro’yhatlar ustida quyidagi amallarni bajarish mumkin.
- ro’yhatni shakllantirish (birinchi elementini yaratish);
- ro’yhat oxiriga yangi element qo’shish;
- berilgan kalitga mos elementni o’qish;
- ro’yhatning ko’rsatilgan joyiga element qo’shish (berilgan kalitga mos elementdan oldin yoki keyin)
- berilgan kalitga mos elementni o’chirish;
- kalit bo’yicha ro’yhat elementlarini tartibga keltirish.
Ro’yhatlar bilan ishlashda dasturda boshlang’ich elementni ko’rsatuvchi ko’lamli ro’yhatlar ustida turli amallar bajarish algoritmlari va dasturlarini ko’rib chiqamiz.
XULOSA:
Men bu mavzudan graflar haqida to’liqroq tushunchaga ega bo’ldim. Graflar bilan axborot texnologiyalari sohasida juda katta yechimlar qilingan va qilsak bo’ladi. Birgina misol tartiblash algoritmini misol qilib keltirishimiz mumkin. Undan tashqari graflar yordamida yana ko’plab kashfiyotlar qilsak bo’ladi. Olimlar bu borada ko’plab izlanishlar olib bormoqda. Ajabmaski, biz ham kelajakda graflar yordamida axborot texnologiyalari va sun’iy intelekt sohalarida kashfiyot qilib juda ham ko’plab va yuqori cho’qilarga erishsak!
| 