Fanidan tayyorlagan

Reja :
1.Graflarni tasvirlash usullari: qo‘shma matrisa Graflarni tasvirlash usullari: munosabatlar matritsasi Graflarni tasvirlash usullari: qo‘shnilik ro‘yxati va yoylar ro‘yxati. Graflarda ko‘ruv algoritmlari.

Grafik tasvirlash usullari - bu grafik ma'lumotlar strukturasini kompyuter xotirasida yoki xotirasida aks ettirish uchun ishlatiladigan usullar. Grafik tasvirlashning turli usullari mavjud, jumladan:

1. Qo'shnilik matritsasi: qo'shnilik matritsasining tasviri grafikni ifodalash uchun ikki o'lchovli matritsadan foydalanadi. Matritsadagi har bir katak ikkita cho'qqi orasidagi chekka mavjudligi yoki yo'qligini ifodalaydi. Yo'naltirilmagan grafik uchun matritsa asosiy diagonal bo'ylab simmetrikdir. Qo'shni matritsa zich grafiklar uchun samarali bo'lib, qirralarning soni maksimal mumkin bo'lgan qirralarga yaqin bo'ladi.

2. Insidans matritsasi: Insidans matritsasi tasviri grafikni ifodalash uchun ikki o'lchovli matritsadan foydalanadi. Matritsaning satrlari cho'qqilarni, ustunlar esa qirralarni ifodalaydi. Matritsadagi har bir yacheyka cho'qqining chetga tushishini ko'rsatadi. Insidans matritsasi odatda vaznli grafiklar yoki yo'naltirilgan grafiklar uchun ishlatiladi.

3. Qo'shnilik ro'yxati: Qo'shnilik ro'yxati tasviri grafikdagi har bir cho'qqi uchun qo'shni cho'qqilar ro'yxatini saqlaydi. Bu siyrak grafiklar uchun xotiradan samaraliroq tasvirdir, bu erda qirralarning soni maksimal mumkin bo'lgan qirralardan ancha kichikdir.

4. Edge List: Chegara ro'yxati tasviri shunchaki grafikdagi barcha qirralarning ro'yxatini ko'rsatadi. U yo'naltirilgan va yo'naltirilmagan grafiklar uchun ishlatilishi mumkin va ixcham vakillikni ta'minlaydi. Biroq, u qo'shni cho'qqilarni olish yoki chekka mavjudligini tekshirish uchun qo'shimcha operatsiyalarni talab qiladi.

Grafiklarni vizualizatsiya qilish algoritmlari grafiklarni displeyda yoki grafik formatda vizual tarzda ko'rsatish uchun ishlatiladi. Ba'zi umumiy grafik vizualizatsiya algoritmlari quyidagilarni o'z ichiga oladi:

1. Majburiy yo'naltirilgan algoritmlar: Bu algoritmlar fizik simulyatsiyalardan foydalanib, grafik tugunlarni chekka o'tishlarni kamaytiradigan va tegishli tugunlarni bir-biriga yaqinroq tutadigan tarzda joylashtiradi. Ular grafik tuzilmasi asosida tugunlarga kuchlarni tayinlaydi va barqaror tuzilishga erishilgunga qadar tugun pozitsiyalarini iterativ ravishda yangilaydi.

2. Circular Layout algoritmlari: Circular maket algoritmlari grafik tugunlarini radial simmetriya bilan yoki ularsiz aylana shaklida joylashtiradi. Ular odatda o'z pozitsiyalarini aniqlash uchun tugunlarning ulanishi va darajasini hisobga oladi.

3. Qatlamli joylashtirish algoritmlari: Qatlamli joylashtirish algoritmlari tugunlarni qatlamlar yoki darajalar bo'yicha tartibga soladi, yo'naltirilgan qirralar yuqoridan pastki qatlamlarga oqib chiqadi. Ular chekka o'tishlarni minimallashtirishga qaratilgan va ko'pincha yo'naltirilgan asiklik grafiklar (DAG) uchun yaxshi ishlaydi.

4. Spring Embedder algoritmlari: Bu algoritmlar grafikni buloqlar va tugunlarning fizik tizimi sifatida modellashtiradi. Ular bog'langan tugunlarga jozibador kuchlarni va barcha tugunlarga itaruvchi kuchlarni belgilaydi, muvozanatga erishilgunga qadar o'z pozitsiyalarini iterativ ravishda moslashtiradi.

Bu grafik vizualizatsiya algoritmlarining bir nechta misollari va boshqa ko'plab texnika va algoritmlar mavjud. Muayyan algoritmni tanlash grafikning o'lchami va tuzilishi, kerakli estetika va maxsus vizualizatsiya talablari kabi omillarga bog'liq.

Breadth First Search - kenglik-birinchi tartibda grafikning barcha cho'qqilarini o'rganadigan, ya'ni keyingi chuqurlik darajasiga o'tishdan oldin bir xil chuqurlikdagi barcha cho'qqilarga tashrif buyuradigan o'tish algoritmidir.

Algoritm ildiz tugunidan (yoki grafikdagi istalgan ixtiyoriy tugun) boshlanadi va qo'shni tugunlarning keyingi darajasiga o'tishdan oldin barcha qo'shni tugunlarga tashrif buyuradi. U tashrif buyuriladigan tugunlarni kuzatib borish uchun navbat ma'lumotlar strukturasidan foydalanadi.

BFS algoritmining bosqichlari quyidagicha:

Depth First Search (DFS) algoritmi:

Depth First Search - bu chizmaning barcha cho'qqilarini chuqur-birinchi tartibda o'rganadigan, ya'ni keyingi cho'qqiga o'tishdan oldin cho'qqining barcha qo'shni tugunlariga tashrif buyuradigan o'tish algoritmidir.

Algoritm ildiz tugunidan (yoki grafikdagi istalgan ixtiyoriy tugundan) boshlanadi va orqaga qaytishdan oldin har bir shoxcha bo'ylab iloji boricha o'rganadi. U tashrif buyuriladigan tugunlarni kuzatib borish uchun stek ma'lumotlar strukturasidan foydalanadi.

DFS algoritmining bosqichlari quyidagicha:
1. Stackni ishga tushiring va boshlang'ich tugunni bosing.
2. Boshlang'ich tugunni tashrif buyurilgan deb belgilang.
3. Stack bo'sh bo'lmasa-da, stekdan tugunni oching.
4. Olingan tugunga tashrif buyuring va uni tashrif buyurilgan deb belgilang.
5. Chiqib ketgan tugunning barcha ko'rilmagan qo'shni tugunlarini stekga suring.
6. Stack bo'sh qolguncha 3 dan 5 gacha bo'lgan bosqichlarni takrorlang.

Ikkala BFS va DFS algoritmlari grafiklarni o'tish uchun ishlatiladi, lekin ular tugunlarga tashrif buyurish tartibida farqlanadi. BFS keyingi chuqurlik darajasiga o'tishdan oldin tugunlarni bir xil chuqurlik darajasida ziyorat qiladi, DFS esa orqaga qaytishdan oldin har bir filial bo'ylab iloji boricha o'rganadi.

1. Dijkstra algoritmi: Bu algoritm manfiy bo'lmagan chekka og'irliklari bo'lgan grafikdagi manba tugun va boshqa barcha tugunlar orasidagi eng qisqa yo'lni topadi. Har bir qadamda minimal masofaga ega tugunni tanlash uchun ustuvor navbatni saqlaydi.

2. Bellman-Ford algoritmi: Bu algoritm manfiy chekka og'irliklari bo'lgan grafiklarni ishlay oladi, lekin salbiy davrlarni aniqlaydi va boshqaradi. U eng qisqa yo'llar topilgunga qadar masofalarni yangilab, qirralarni takroriy bo'shashtiradi.

3. A* Qidiruv algoritmi: Bu algoritm samaradorlikni oshirish uchun Dijkstra algoritmini evristika bilan birlashtiradi. Joriy tugundan belgilangan manzilgacha bo'lgan xarajatlarni baholash uchun smeta funktsiyasidan foydalanadi va eng past taxminiy umumiy xarajat bilan yo'lni tanlaydi.

Grafiklardagi eng qisqa yo'lni aniqlash muammolari:

1. Yagona manbali eng qisqa yo'l (SSSP): Bu muammo bitta manba tugunidan grafikdagi barcha boshqa tugunlarga eng qisqa yo'lni topishni o'z ichiga oladi. SSSP uchun Dijkstra algoritmi va Bellman-Ford algoritmi keng tarqalgan.

2. Bir juftlik eng qisqa yo'l (SPSP): Bu masalada maqsad grafikdagi ikkita aniq tugun orasidagi eng qisqa yo'lni topishdir. SPSP uchun Dijkstra algoritmi va A* qidiruv algoritmidan foydalanish mumkin.

3. All-Pairs Shortest Path (APSP): APSP muammosi grafikdagi barcha juft tugunlar orasidagi eng qisqa yo'lni topishga qaratilgan. APSP uchun odatda Floyd-Uorshall algoritmi va Jonson algoritmidan foydalaniladi.

Grafiklardagi eng qisqa yo'lni aniqlash uchun algoritmlarni tahlil qilish:

Ushbu algoritmlarning vaqt murakkabligi grafik xususiyatlariga va foydalanilgan algoritmga qarab o'zgaradi. O'rtacha, Dijkstra algoritmi O ((V + E) log V vaqt murakkabligiga ega, bu erda V - tepalar soni va E - qirralarning soni. Bellman-Ford algoritmi vaqt murakkabligi O(VE) ga ega, bu esa uni Dijkstra algoritmiga qaraganda unumliroq qiladi.

A* qidiruv algoritmining vaqt murakkabligi ishlatiladigan evristik funktsiyaning sifatiga bog'liq. Eng yaxshi hollarda, u Dijkstra algoritmi kabi samarali bo'lishi mumkin, lekin eng yomon hollarda u eksponent bo'lishi mumkin.

Floyd-Uorshall algoritmi vaqt murakkabligi O(V^3) bo‘lib, uni kichik grafiklar uchun mos qiladi. Jonson algoritmi vaqt murakkabligi O(V^2 log V + VE), bu yerda V cho'qqilar soni, E - qirralarning soni.

Xotiradan foydalanish nuqtai nazaridan kosmik murakkablik ham ushbu algoritmlar orasida farq qiladi. Dijkstra algoritmi va Bellman-Ford algoritmi uchun O(V) qoʻshimcha joy talab qilinadi, Floyd-Uorshall algoritmi esa O(V^2) qoʻshimcha joy talab qiladi. A* qidiruv algoritmi ustuvor navbatni saqlash uchun qo'shimcha xotirani ham talab qiladi.
Floyd-Uorshall algoritmi, Floyd algoritmi yoki Floydning All-Pairs Shortest Path algoritmi sifatida ham tanilgan, All-Pairs Shortest Path muammosini hal qilish uchun ishlatiladi. U grafikdagi barcha tugun juftlari orasidagi eng qisqa yo'llarni hisoblab chiqadi, hatto manfiy og'irlikdagi grafiklar uchun ham.

Algoritm iterativ ravishda barcha oraliq tugunlarni eng qisqa yo'lda mumkin bo'lgan oraliq qadam sifatida ko'rib chiqish orqali ishlaydi. U eng qisqa yo'llar aniqlanmaguncha tugunlar juftlari orasidagi masofani yangilaydi.

Floyd-Uorshall algoritmining qisqacha tavsifi:

1. Grafikdagi juft tugunlar orasidagi masofani ifodalovchi masofa matritsasi deb ataladigan matritsa yarating. Matritsani tugunlar orasidagi to'g'ridan-to'g'ri masofalar va to'g'ridan-to'g'ri aloqasi bo'lmagan juft tugunlar uchun cheksizlik bilan boshlang.

2. Barcha mumkin bo'lgan oraliq tugunlarni (k) 1 dan grafikdagi tugunlar sonigacha takrorlang.

3. Har bir juft tugun (i, j) uchun k tugunini oraliq bosqich sifatida kiritish orqali i va j orasidagi masofani qisqartirish mumkinligini tekshiring. Masofa matritsasini mos ravishda yangilang.

Jarayon barcha mumkin bo'lgan oraliq tugunlar uchun barcha tugun juftlari ko'rib chiqilgunga qadar takrorlanadi. Algoritm tugallangandan so'ng, masofa matritsasi barcha tugun juftlari orasidagi eng qisqa yo'llarni o'z ichiga oladi.

Floyd-Uorshall algoritmining vaqt murakkabligi O(V^3) ga teng, bu erda V - grafikdagi uchlari soni. Masofa matritsasini saqlash uchun fazo murakkabligi O(V^2).

Shuni ta'kidlash kerakki, Floyd-Uorshall algoritmidan grafikdagi salbiy sikllarni aniqlash uchun ham foydalanish mumkin. Algoritmni bajarish jarayonida har qanday manfiy sikllar aniqlansa, bu grafikning eng qisqa yo'llari yo'qligini ko'rsatadi, chunki salbiy sikl cheksiz qisqa yo'llarga imkon beradi.
Ford-Bellman algoritmi:
Ford-Bellman algoritmi vaznli yo'naltirilgan grafikdagi manba tugunidan boshqa barcha tugunlarga eng qisqa yo'lni topish uchun ishlatiladi. U salbiy qirrali og'irliklarga bardosh bera oladi, ammo salbiy tsikllarni boshqara olmaydi. Algoritm qanday ishlaydi:

1. 0 ga o'rnatilgan manba tugunining o'zi bundan mustasno, manba tugunidan barcha tugunlarning masofasini cheksizlik sifatida boshlang.

2. Quyidagi amallarni V-1 marta takrorlang, bu erda V - grafikdagi cho'qqilar soni:
a. Grafikning barcha qirralari bo'ylab takrorlang
b. Og'irligi w bo'lgan har bir chekka (u, v) uchun v ning masofasini uning joriy masofasining minimumi va u va og'irlik w ning masofasi sifatida yangilang.

3. V-1 iteratsiyalaridan so'ng, masofa massivi manba tugunidan boshqa barcha tugunlargacha bo'lgan eng qisqa masofalarni o'z ichiga oladi.

Ford-Bellman algoritmining vaqt murakkabligi O (V * E) ga teng, bu erda V - cho'qqilar soni va E - grafikdagi qirralarning soni.

Dijkstra algoritmi:

1. 0 ga o'rnatilgan manba tugunining o'zi bundan mustasno, manba tugunidan barcha tugunlarning masofasini cheksizlik sifatida boshlang.

2. Joriy masofani ustuvorlik sifatida ishlatib, tugunlarni masofalari bilan saqlash uchun ustuvor navbat yarating.

3. Ustuvor navbat boʻsh qolguncha quyidagi amallarni takrorlang:

4. Algoritm tugallangandan so'ng, masofa massivi manba tugunidan boshqa barcha tugunlargacha bo'lgan eng qisqa masofalarni o'z ichiga oladi.

Dijkstra algoritmining vaqt murakkabligi O((V + E) log V dir), bu yerda V - uchlari soni, E - grafikdagi qirralarning soni.

Ustuvor navbatlar:

Dijkstra algoritmi holatida, ustuvor navbat tugunlarni manba tugunidan masofalari bilan birga saqlash uchun ishlatiladi. Eng kichik masofaga ega bo'lgan tugun har doim navbatning old qismida bo'lib, minimal masofa bilan tugunga samarali kirish imkonini beradi.

Lug'atlar va ularni amalga oshirish:
Algoritmlar va ma'lumotlar tuzilmalari kontekstida lug'at (shuningdek, xarita yoki assotsiativ massiv sifatida ham tanilgan) har bir kalit noyob va qiymat bilan bog'langan kalit-qiymat juftliklari to'plamidir. Lug'atlar ularning kalitlari asosida elementlarni samarali qidirish, kiritish va o'chirish imkonini beradi.

Lug'atlarni amalga oshirish dasturlash tiliga yoki ma'lumotlar strukturasi kutubxonalariga qarab farq qilishi mumkin. Masalan, lug'atlar massivlar, bog'langan ro'yxatlar, xesh jadvallari yoki muvozanatli qidiruv daraxtlari yordamida amalga oshirilishi mumkin.

Python kabi tillarda lug'atlar hash-jadvallar yordamida amalga oshiriladi, ular tez o'rtacha harflarni qidirish, kiritish va o'chirish operatsiyalarini ta'minlaydi. Xesh-jadvallar kalitlarni asosiy massivdagi indekslarga solishtirish uchun xesh funktsiyasidan foydalanadi, bu esa o'rtacha holatda doimiy kirish imkonini beradi.

Boshqa tillar yoki kutubxonalar vaqt murakkabligi va xotiradan foydalanish o'rtasida turli xil lug'at dasturlarini taqdim etishi mumkin.