6-laboratoriya mashg’uloti graflar. Umumiy ma’lumotlar Graf

Grafni tasvirlash usullari
Grafni tasvirlash uchun bir nechta usullardan foydalaniladi. Graflardan o'tish uchun siz o'zingizning muammoingizni eng samarali hal qiladiganlardan foydalanishingiz kerak. Ko'pincha, tanlov qo'shnilik matritsasi va qo'shnilik ro'yxati o'rtasida bo'ladi (quyidagi jadval ikkala yondashuvning samaradorligini taqqoslaydi). Shu bilan birga, o'rnatilgan C-massivga tayanib, o'zingizning ma'lumotlar tuzilmalaringizni modellashtirishingiz va STD-da mavjud bo'lgan turli xil konteynerlardan foydalanishingiz mumkin.


Qo’shnilik matritsasi
1 dan n gacha raqamlangan G grafning qo'shnilik matritsasi kvadrat kattalikdagi A matritsasi bo'lib, unda a [i][j] elementining qiymati 1 ga teng bo'lsa, grafning i- va j- uchlari qo’shni bo‘ladi, aks holda qiymati nolga teng bo‘ladi. Bunday matritsa binar matritsa deb ham ataladi. Oddiy graf uchun asosiy diagonal elementlari 0 ga teng bo‘ladi.
Qo'shnilik matritsasi orgrafni tavsiflash uchun ham, yo'naltirilmagan grafni tasvirlash uchun ham mos keladi. Yo'naltirilmagan graf uchun elementlarning qiymatlari asosiy diagonalga nisbatan nosimmetrikdir.
Qo'shnilik matritsadan foydalanish faqat qirralari ko'p bo'lmagan hamda murakkab bo‘lmagan graflar uchun afzalroqdir, chunki u har bir element uchun bitta bit saqlashni talab qiladi. Agar graf murakkab bo'lsa, unda xotiraning katta qismi nollarni saqlashga sarflanadi, ammo murakkab graflarda qo'shnilik matritsasi grafni xotirada ixchamroq ifodalaydi va taxminan bit xotiradan foydalanadi. Ushbu kattalik qo'shnilik ro'yxatlariga qaraganda yaxshiroq (pastga qarang).
3-rasm. Yo’naltirilmagan grafda qo’shnilik matritsasi

4-rasm. Orgrafda qo’shnilik matritsasi
Qo'shnilik matritsasini amalga oshirish uchun massivlar massivi qo'llaniladi: vektorlar vektori (vector>) yoki kaliti uchlar soni, qiymati esa vektori. Agar grafni kengaytirish kerak bo'lmasa, u holda vektorni array (massiv) bilan almashtirish kerak.