DSA graflar
Graflar
Graf — cho‘qqilar (tugunlar) va qirralardan tashkil topgan nochiziqli ma’lumotlar tuzilmasi.
Cho‘qqi, ya’ni tugun — grafdagi nuqta yoki obyekt, qirra esa ikki cho‘qqini bir-biri bilan bog‘lash uchun ishlatiladi.
Graflar nochiziqli hisoblanadi, chunki bu ma’lumotlar tuzilmasi massivlar yoki bog‘langan ro‘yxatlar kabi chiziqli ma’lumotlar tuzilmalaridan farqli ravishda bir cho‘qqidan boshqasiga borish uchun turli yo‘llarga ega bo‘lish imkonini beradi.
Graflar ma’lumotlar obyektlar va ular orasidagi munosabatlardan iborat bo‘lgan masalalarni ifodalash va hal qilish uchun ishlatiladi, masalan:
- Ijtimoiy tarmoqlar: har bir odam — cho‘qqi, munosabatlar (masalan, do‘stlik) esa qirralar. Algoritmlar potensial do‘stlarni taklif qilishi mumkin.
- Xaritalar va navigatsiya: shahar yoki avtobus bekatlari kabi joylar cho‘qqilar sifatida, yo‘llar esa qirralar sifatida saqlanadi. Graf ko‘rinishida saqlanganda algoritmlar ikki joy orasidagi eng qisqa marshrutni topishi mumkin.
- Internet: veb-sahifalar cho‘qqilar, giperhavolalar esa qirralar sifatida graf ko‘rinishida ifodalanishi mumkin.
- Biologiya: graflar neyron tarmoqlar yoki kasalliklarning tarqalishi kabi tizimlarni modellashtirishi mumkin.
Graf xususiyatlari
Turli graf xususiyatlarini va bu xususiyatlarni qanday birlashtirish mumkinligini tushunish uchun quyidagi animatsiyadan foydalaning.
Vaznli graf — qirralari qiymatlarga ega bo‘lgan graf. Qirraning vazn qiymati masofa, sig‘im, vaqt yoki ehtimollik kabi narsalarni ifodalashi mumkin.
Bog‘lamli graf — barcha cho‘qqilari qandaydir tarzda qirralar orqali bog‘langan graf. Bog‘lamli bo‘lmagan graf — ajralgan (o‘zaro kesishmaydigan) qism graflarga yoki alohida yakka cho‘qqilarga ega graf.
Yo‘naltirilgan graf, shuningdek digraf deb ham ataladi, — cho‘qqilar juftlari orasidagi qirralar yo‘nalishga ega bo‘lgan graf. Qirraning yo‘nalishi iyerarxiya yoki oqim kabi narsalarni ifodalashi mumkin.
Siklik graf yo‘naltirilgan yoki yo‘naltirilmaganligiga qarab turlicha ta’riflanadi:
- Yo‘naltirilgan siklik graf — yo‘naltirilgan qirralar bo‘ylab aylana hosil qiluvchi yo‘ldan yurish mumkin bo‘lgan graf. Yuqoridagi animatsiyada F’dan G’ga yo‘naltirilgan qirrani olib tashlash yo‘naltirilgan grafni endi siklik bo‘lmaydigan qiladi.
- Yo‘naltirilmagan siklik graf — bitta qirradan bir martadan ortiq foydalanmasdan boshlagan cho‘qqingizga qaytib kelish mumkin bo‘lgan graf. Yuqoridagi yo‘naltirilmagan graf siklik, chunki biz bitta qirradan ikki marta foydalanmasdan C cho‘qqisidan boshlab, yana unda tugatishimiz mumkin.
Halqa (loop), shuningdek o‘z-o‘ziga halqa (self-loop) deb ham ataladi, — bitta cho‘qqida boshlanib, o‘sha cho‘qqida tugaydigan qirra. Halqa — faqat bitta qirradan iborat sikl. Yuqoridagi animatsiyada A cho‘qqisiga halqa qo‘shish orqali graf siklik bo‘ladi.
Graflarni ifodalash usullari
Grafni ifodalash usuli graf xotirada qanday saqlanishini ko‘rsatadi.
Grafni ifodalashning turli usullari:
- ko‘proq yoki kamroq joy egallashi mumkin.
- qidirish yoki o‘zgartirish uchun tezroq yoki sekinroq bo‘lishi mumkin.
- qanday turdagi grafga egaligimiz (vaznli, yo‘naltirilgan va h.k.) hamda graf bilan nima qilmoqchi ekanligimizga qarab mosroq bo‘lishi mumkin.
- boshqalariga qaraganda tushunish va amalga oshirish uchun osonroq bo‘lishi mumkin.
Quyida grafni ifodalashning turli usullari bilan qisqacha tanishtiriladi, ammo ushbu darslikda bundan buyon graflar uchun qo‘shnilik matritsasidan foydalanamiz, chunki uni tushunish va amalga oshirish oson hamda u ushbu darslikka tegishli barcha holatlarda ishlaydi.
Grafni ifodalash usullari qaysi cho‘qqilar qo‘shni ekanligi va cho‘qqilar orasidagi qirralar qandayligi haqidagi ma’lumotni saqlaydi. Qirralar yo‘naltirilgan yoki vaznli bo‘lsa, grafni ifodalash usullari biroz farq qiladi.
Agar ikki cho‘qqi orasida qirra bo‘lsa, ular qo‘shni hisoblanadi.
Grafni qo‘shnilik matritsasi orqali ifodalash
Qo‘shnilik matritsasi — ushbu darslikda foydalanadigan grafni ifodalash usuli (tuzilmasi).
Qo‘shnilik matritsasini qanday amalga oshirish keyingi sahifada ko‘rsatilgan.
Qo‘shnilik matritsasi — ikki o‘lchovli massiv (matritsa) bo‘lib, undagi (i,j) indeksidagi har bir katak i cho‘qqidan j cho‘qqiga boruvchi qirra haqidagi ma’lumotni saqlaydi.
Quyida graf va uning yonida qo‘shnilik matritsasi ko‘rinishidagi ifodasi berilgan.
va qo‘shnilik matritsasi
Yuqoridagi qo‘shnilik matritsasi yo‘naltirilmagan grafni ifodalaydi, shuning uchun '1' qiymatlari faqat qirralar qayerda ekanini ko‘rsatadi. Shuningdek, qo‘shnilik matritsasidagi qiymatlar simmetrik, chunki qirralar ikkala tomonga yo‘nalgan (yo‘naltirilmagan graf).
Qo‘shnilik matritsasi yordamida yo‘naltirilgan graf yaratish uchun qiymatni to‘g‘ri indekslarga (i,j) qo‘yish orqali qirralar qaysi cho‘qqilardan qaysi cho‘qqilarga borishini belgilashimiz kerak. Vaznli grafni ifodalash uchun qo‘shnilik matritsasiga '1' dan boshqa qiymatlarni qo‘yishimiz mumkin.
Quyida yo‘naltirilgan va vaznli graf va uning yonida qo‘shnilik matritsasi ko‘rinishidagi ifodasi berilgan.
va uning qo‘shnilik matritsasi.
Yuqoridagi qo‘shnilik matritsasida (0,1) indeksidagi 3 qiymati A cho‘qqisidan B cho‘qqisiga qirra borligini va bu qirraning vazni 3 ekanini bildiradi.
Ko‘rib turganingizdek, vaznlar qo‘shnilik matritsasiga to‘g‘ridan-to‘g‘ri tegishli qirra uchun joylashtiriladi va yo‘naltirilgan graf uchun qo‘shnilik matritsasi simmetrik bo‘lishi shart emas.
Grafni qo‘shnilik ro‘yxati orqali ifodalash
Agar bizda ko‘p cho‘qqili 'siyrak' graf bo‘lsa, qo‘shnilik matritsasi o‘rniga qo‘shnilik ro‘yxatidan foydalanib joyni tejashimiz mumkin, chunki qo‘shnilik matritsasi mavjud bo‘lmagan qirralar uchun bo‘sh massiv elementlariga ko‘p xotira ajratib qo‘yadi.
'Siyrak' graf — har bir cho‘qqi grafdagi boshqa cho‘qqilarning faqat kichik qismi bilan qirralarga ega bo‘lgan graf.
Qo‘shnilik ro‘yxati grafdagi barcha cho‘qqilarni o‘z ichiga olgan massivga ega va har bir cho‘qqi o‘z qirralari saqlanadigan bog‘langan ro‘yxatga (yoki massivga) ega.
va uning qo‘shnilik ro‘yxati.
Yuqoridagi qo‘shnilik ro‘yxatida A dan D gacha bo‘lgan cho‘qqilar massivga joylashtirilgan va massivdagi har bir cho‘qqining indeksi uning yonida yozilgan.
Massivdagi har bir cho‘qqi o‘sha cho‘qqining qirralarini ifodalovchi bog‘langan ro‘yxatga ko‘rsatkichga ega. Aniqroq aytganda, bog‘langan ro‘yxatda qo‘shni cho‘qqilarning indekslari saqlanadi.
Masalan, A cho‘qqisi 3, 1 va 2 qiymatli bog‘langan ro‘yxatga havolaga ega. Bu qiymatlar A’ning qo‘shni cho‘qqilari D, B va C’ning indekslari.
Qo‘shnilik ro‘yxati yo‘naltirilgan va vaznli grafni ham quyidagicha ifodalashi mumkin:
va uning qo‘shnilik ro‘yxati.
Yuqoridagi qo‘shnilik ro‘yxatida cho‘qqilar massivda saqlanadi. Har bir cho‘qqi qirralari i,w ko‘rinishida saqlangan bog‘langan ro‘yxatga ko‘rsatkichga ega, bu yerda i — qirra boradigan cho‘qqining indeksi, w esa o‘sha qirraning vazni.
Masalan, D tugunida A cho‘qqisiga boruvchi qirraga ega bog‘langan ro‘yxatga ko‘rsatkich bor. 0,4 qiymatlari D cho‘qqisidan 0 indeksidagi cho‘qqiga (A cho‘qqisiga) qirra borligini va o‘sha qirraning vazni 4 ekanini bildiradi.
DSA mashqlari
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!