Graflar
Grafiklar
Grafik chiziqli bo‘lmagan ma’lumotlar strukturasi bo‘lib, u tepalar (tugunlar) va qirralardan iborat.
Cho‘qqi, shuningdek, tugun deb ataladi, Grafikdagi nuqta yoki obyekt bo‘lib, chekka ikkita cho‘qqini bir-biriga ulash uchun ishlatiladi.
Grafiklar chiziqli emas, chunki ma’lumotlar strukturasi massivlar yoki bog‘langan listlar kabi chiziqli ma’lumotlar tuzilmalaridan farqli o‘laroq, bir cho‘qqidan ikkinchisiga o‘tish uchun turli yo‘llarga ega bo‘lish imkonini beradi.
Grafiklar ma’lumotlar obyektlar va ular orasidagi munosabatlardan iborat bo‘lgan muammolarni ko‘rsatish va hal qilish uchun ishlatiladi, masalan:
- Ijtimoiy tarmoqlar: Har bir inson bir cho‘qqidir va munosabatlar (do‘stlik kabi) qirralardir. Algoritmlar potentsial do‘stlarni taklif qilishi mumkin.
- Xaritalar va navigatsiya: shahar yoki avtobus bekatlari kabi joylar cho‘qqilar, yo‘llar esa chekkalar sifatida saqlanadi. Joylar graf sifatida saqlanganda algoritmlar ikki joy orasidagi eng qisqa yo‘lni topishi mumkin.
- Internet: Grafik sifatida tasvirlanishi mumkin, veb-sahifalar cho‘qqilar, giperhavolalar esa qirralar sifatida.
- Biologiya: Grafiklar neyron tarmoqlar yoki kasalliklar tarqalishi kabi tizimlarni modellashtirishi mumkin.
Grafik tasvirlar
Grafik tasviri bizga grafik xotirada qanday saqlanganligini aytadi.
Grafni tasvirlashning turli usullari:
- ko‘proq yoki kamroq joy egallaydi.
- qidirish yoki manipulyatsiya qilish uchun tezroq yoki sekinroq bo‘ling.
- Grafikning qaysi turiga (vaznlangan, yo‘naltirilgan va hokazo) va biz grafik bilan nima qilishni xohlayotganimizga qarab yaxshiroq mos bo‘lishi kerak.
- tushunish va amalga oshirish boshqalarga qaraganda osonroq.
Quyida turli xil grafik tasvirlar haqida qisqacha ma’lumot berilgan, ammo qo‘shnilik matritsasi biz ushbu o‘quv qo‘llanmada oldinga siljiydigan Grafiklar uchun foydalanamiz, chunki uni tushunish va amalga oshirish oson va ushbu qo‘llanmaga tegishli barcha holatlarda ishlaydi.
Grafik tasvirlar qaysi cho‘qqilar qo‘shni ekanligi va cho‘qqilar orasidagi qirralarning qanday ekanligi haqidagi ma’lumotlarni saqlaydi. Agar qirralar yo‘naltirilgan yoki og‘irlashtirilgan bo‘lsa, grafik tasvirlar biroz farq qiladi.
Ikki cho‘qqi qo‘shni yoki qo‘shni, agar ular orasida chekka bo‘lsa.
Qo‘shnilik matritsasi grafik tasviri
Qo‘shnilik matritsasi - bu biz ushbu qo‘llanma uchun foydalanadigan grafik tasviri (tuzilmasi).
Qo‘shnilik matritsasi qanday amalga oshirilishi keyingi sahifada ko‘rsatilgan.
Qo‘shnilik matritsasi 2D massiv (matritsa) bo‘lib, unda (i,j)indeksidagi har bir katak i cho‘qqidan j cho‘qqigacha bo‘lgan chekka haqidagi ma’lumotlarni saqlaydi.
Quyida uning yonidagi qo‘shnilik matritsasi tasvirlangan grafik mavjud.
va qo‘shnilik matritsasi
Yuqoridagi qo‘shnilik matritsasi yo‘naltirilmagan Grafikni ifodalaydi, shuning uchun "1" qiymatlari faqat qirralarning qayerda ekanligini ko‘rsatadi. Bundan tashqari, qo‘shni matritsadagi qiymatlar nosimmetrikdir, chunki qirralar ikkala tomonga ham boradi (yo‘naltirilmagan Grafik).
Qo‘shni matritsaga ega yo‘naltirilgan Grafikni yaratish uchun biz (i,j) to‘g‘ri indekslarga qiymat qo‘yish orqali qirralarning qaysi cho‘qqilardan va tomonga ketishini hal qilishimiz kerak. Og‘irlangan Grafikni ko‘rsatish uchun biz qo‘shni matritsa ichiga "1" dan boshqa qiymatlarni qo‘yishimiz mumkin.
Quyida qo‘shnilik matritsasi tasviri bilan yo‘naltirilgan va vaznli grafik mavjud.
hamda uning qo‘shnilik matritsasi.
Yuqoridagi qo‘shnilik matritsasida (0,1) indeksidagi 3 qiymati A cho‘qqidan B cho‘qqigacha chekka borligini va bu chekkaning og‘irligi 3 ga teng ekanligini bildiradi.
Ko‘rib turganingizdek, og‘irliklar to‘g‘ri chekka uchun to‘g‘ridan-to‘g‘ri qo‘shni matritsaga joylashtiriladi va yo‘naltirilgan Grafik uchun qo‘shnilik matritsasi simmetrik bo‘lishi shart emas.
Qo‘shnilik ro‘yxatining grafik tasviri
Agar bizda ko‘p uchlari bo‘lgan "siyrak" grafik mavjud bo‘lsa, biz qo‘shnilik matritsasidan foydalanish bilan solishtirganda qo‘shnilik ro‘yxatidan foydalanib bo‘sh joyni tejashimiz mumkin, chunki qo‘shnilik matritsasi mavjud bo‘lmagan qirralar uchun bo‘sh Massiv elementlarida juda ko‘p xotirani saqlab qo‘yadi.
"Seyk" grafik - bu grafik, unda har bir cho‘qqi faqat grafikdagi boshqa cho‘qqilarning kichik bir qismiga chekkalari bo‘ladi.
Qo‘shnilik ro‘yxatida Grafikning barcha uchlarini o‘z ichiga olgan massiv mavjud va har bir tepada cho‘qqi qirralari bilan bog‘langan list (yoki massiv) mavjud.
va uning qo‘shnilik ro‘yxati.
Yuqoridagi qo‘shnilik ro‘yxatida A dan D gacha cho‘qqilar massivga joylashtirilgan va massivdagi har bir cho‘qqi o‘zining indeksi yonida yozilgan.
Massivdagi har bir cho‘qqi o‘sha cho‘qqining chetlarini ifodalovchi Bog‘langan listga ko‘rsatgichga ega. Aniqroq qilib aytganda, Bog‘langan list qo‘shni (qo‘shni) uchlari indekslarini o‘z ichiga oladi.
Masalan, A cho‘qqisida 3, 1 va 2 qiymatlari bo‘lgan Bog‘langan listga havola mavjud. Bu qiymatlar A ning qo‘shni D, B va C cho‘qqilarining indekslaridir.
Qo‘shnilik ro‘yxati yo‘naltirilgan va og‘irlashtirilgan grafikni ham ko‘rsatishi mumkin, masalan:
hamda uning qo‘shnilik ro‘yxati.
Yuqoridagi qo‘shnilik ro‘yxatida uchlari massivda saqlanadi. Har bir cho‘qqi i,w sifatida saqlangan qirralari bilan bog‘langan listga ko‘rsatgichga ega, bu yerda i - chekka boradigan cho‘qqining indeksi va w - bu chekkaning og‘irligi.
Masalan, D tugunida A cho‘qqigacha bo‘lgan bog‘langan list ko‘rsatkichi mavjud.0,4 qiymatlari D cho‘qqi 0 indeksida (A cho‘qqi) cho‘qqigacha ega ekanligini va bu chekkaning og‘irligi 4 ga teng ekanligini bildiradi.
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!