|
Muhammad Al-Xorazmiy nomida Toshkent Axborot texnologiyalari universiteti Mustaqil ish Mavzu
|
| bet | 2/2 | | Sana | 25.12.2023 | | Hajmi | 0,68 Mb. | | #128293 |
Bog'liq 40 variantDeykstra algoritmining tadbiqi
Grafning og’irligini saqlash uchun kvadrat matritsadan foydalaniladi. Satrlar va ustunlar sarlavhalarida grafning uchlari joylashadi. Graf yoylarining og’irligi jadvalning ichki yacheykalariga joylashtiriladi. Graf petlyaga ega emas, shu sababdan ham matritsaning asosiy diagonalida nol qiymatlar joylashgan.
Grafikni 3 ta ma'lumotlar tuzilmasi - qo'shnilik matritsasi, qo'shnilik ro'yxati va qo'shnilik to'plami yordamida tasvirlash mumkin.
Qo'shnilik matritsasi qatorlar va ustunlardan iborat jadval sifatida ko'rib chiqilishi mumkin. Qator va ustun yorliqlari grafik tugunlarini ifodalaydi. Qo'shni matritsa - bu qatorlar, ustunlar va tugunlar soni bir xil bo'lgan kvadrat matritsa. Matritsaning har bir yacheykasi chekka yoki ikkita berilgan tugun orasidagi munosabatni ifodalaydi. Masalan, Aij qo'shnilik matritsasi ikkita i va j tugunlari berilgan i dan j gacha bo'lgan bog'lanishlar sonini ifodalaydi.
|
A
|
B
|
C
|
D
|
E
|
A
|
0
|
0
|
0
|
0
|
1
|
B
|
0
|
0
|
1
|
0
|
0
|
C
|
0
|
1
|
0
|
0
|
1
|
D
|
1
|
0
|
0
|
1
|
0
|
E
|
0
|
1
|
1
|
0
|
0
|
Yo'naltirilgan grafik uchun qo'shnilik matritsasi 3-rasmda ko'rsatilgan. E'tibor bering, u kvadrat matritsa bo'lib, unda qatorlar, ustunlar va tugunlar soni bir xil bo'lib qoladi (bu holda 5). Har bir satr va ustun grafikning tuguniga yoki tepasiga mos keladi. Matritsa ichidagi hujayralar tugunlar orasidagi aloqani ifodalaydi. Berilgan yo'naltirilgan grafikda hech qanday tugun o'zi bilan bog'lanmaganligi sababli, matritsaning diagonalida joylashgan barcha katakchalar nolga teng. Qolgan hujayralar uchun, agar berilgan tugundan boshqasiga yo'naltirilgan chekka mavjud bo'lsa, unda mos keladigan katak boshqa nol bilan belgilanadi.
Yo'naltirilmagan grafikni qo'shni matritsa yordamida qanday tasvirlash mumkinligini tushunish uchun beshta cho'qqisi bo'lgan kichik yo'naltirilmagan grafikni ko'rib chiqing (4-rasm). Bu erda A B ga ulanadi, lekin B ham A ga ulanadi. Demak, ikkala katakcha ham, ya'ni A manbasi B maqsadli, ikkinchisi B manba manzili A bo'lgan hujayralar bittasi bilan belgilanadi. Bu yo'naltirilmagan chekka talabi uchun etarli. E'tibor bering, ikkinchi yozuv asosiy diagonal bo'ylab aks ettirilgan joyda joylashgan.
Og'irlangan grafik bo'lsa, hujayralar o'rniga chekka og'irliklar bilan belgilanadi. 5-rasmda B va D chekka tutashtiruvchi tugunlarga berilgan og‘irlik 3 ga teng. Demak, qo‘shnilik matritsasining mos keladigan katakchalari, ya’ni B qatori D ustuni va D qatori B ustuni 3 deb belgilangan.
NetworkX kutubxonasi qo'shni matritsalarni yaratishning oson usulini taqdim etadi. Quyidagi misol NetworkX yordamida asosiy qo'shnilik matritsasini qanday yaratishimiz mumkinligini ko'rsatadi.
Grafikning qo'shni ro'yxatini ko'rsatishda har bir tepa tugun ob'ekti sifatida taqdim etiladi. Tugun ma'lumotlarni yoki bog'langan ro'yxatga havolani o'z ichiga olishi mumkin. Ushbu bog'langan ro'yxat joriy tugunga ulashgan barcha tugunlar ro'yxatini taqdim etadi. A tugunini va B tugunini birlashtiruvchi chekkadan iborat grafikni ko'rib chiqing. Keyin A tugun B tugunining bog'langan ro'yxatida mavjud bo'ladi. 6-rasmda 5 ta tugunning namunaviy grafigi va unga mos keladigan qo'shnilik ro'yxati ko'rsatilgan.
E'tibor bering, E tuguniga mos keladigan ro'yxat bo'sh, B va D tugunlariga mos keladigan ro'yxatlarning har birida 2 ta yozuv mavjud.
Xuddi shunday, yo'naltirilmagan grafik uchun qo'shni ro'yxatlar ham tuzilishi mumkin. Yaxshiroq tushunish uchun 7-rasmda yo'naltirilmagan grafik misoli va uning qo'shnilik ro'yxati keltirilgan.
Qo'shnilar ro'yxati qo'shni matritsaga nisbatan tezroq qidirish jarayonini ta'minlaydi. Biroq, bu, ayniqsa tugunlarni qo'shish yoki o'chirish haqida gap ketganda, grafiklarning eng yaxshi ko'rinishi emas. Masalan, tugunni o'chirish ma'lum bir tugunni barcha ro'yxatlardan olib tashlash uchun barcha qo'shni ro'yxatlarni ko'rib chiqishni o'z ichiga oladi. NetworkX kutubxonasi berilgan grafikning qo'shnilik ro'yxatini yaratish uchun adjacency_list () funktsiyasini taqdim etadi . Quyidagi kod uning ishlatilishini ko'rsatadi.
Qo'shnilar to'plami qo'shnilar ro'yxatidan kelib chiqadigan ba'zi qiyinchiliklarni engillashtiradi. Qo'shnilik to'plami qo'shnilar ro'yxatiga juda o'xshaydi, faqat bog'langan ro'yxat o'rniga; qo'shni cho'qqilar to'plami taqdim etiladi. Qo'shnilik ro'yxati va to'plami ko'pincha tugunlar orasidagi bog'lanishlar kam bo'lgan siyrak grafiklar uchun ishlatiladi. Aksincha, qo'shnilik matritsasi ko'plab tugunlarni o'z ichiga olgan yaxshi bog'langan grafiklar uchun yaxshi ishlaydi.
Chiziqli qidirish algoritmi qanday ishlaydi
Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga ham oson.
Arrayning birinchi elementidan tekshirish boshlanadi.
Element olinadi va u berilgan shartga tekshirib ko’riladi.
Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki shunchaki true) qaytariladi va algoritm tugaydi.
Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladi
Array tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1 yoki false…)
Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.
Algoritm implementatsiyasiga o’zingiz mustaqil harakat qilib ko’ring, yoki keyingi videodarsimizga o’ting.
Algoritm murakkabligi
Giraflar haqida yana bitta dastur
Qo'shma matrisa usullari C++ tilida graf ifodalanish uchun yordamchi bo'lishi mumkin. Bu usullar grafning to'g'ridan-to'g'ri qo'shish (adjacency) yoki bog'liqlik (incidence) matrisalariga asoslangan.
Mana bu oddiy misol, C++ tilida qo'shma matrisa yordamida graf yaratish:
#include
#include
using namespace std;
class Graph {
int vertexCount; // Tugunlar soni
vector> adjacencyMatrix; // Adjansiya matrisa
public:
Graph(int vertices) : vertexCount(vertices) {
// Matrisani bo'shatish
for (int i = 0; i < vertexCount; ++i) {
vector row(vertexCount, 0);
adjacencyMatrix.push_back(row);
}
}
// Grafga yon birligi (edge) qo'shish
void addEdge(int fromVertex, int toVertex) {
adjacencyMatrix[fromVertex][toVertex] = 1;
// Undirected graph uchun
adjacencyMatrix[toVertex][fromVertex] = 1;
}
// Grafni ko'rsatish
void displayGraph() {
for (int i = 0; i < vertexCount; ++i) {
for (int j = 0; j < vertexCount; ++j) {
cout << adjacencyMatrix[i][j] << " ";
}
cout << endl;
}
}
};
int main() {
// Graf obyekti yaratish
Graph myGraph(5);
// Tugunlarga yon birligini qo'shish
myGraph.addEdge(0, 1);
myGraph.addEdge(0, 2);
myGraph.addEdge(1, 3);
myGraph.addEdge(2, 4);
// Grafni ko'rsatish
myGraph.displayGraph();
return 0;
}
Ushbu kodda, Graph klassi yaratilgan va undan foydalanilarak addEdge metodi orqali grafga yon birligi qo'shiladi. displayGraph metodi esa grafning qo'shma matrisasini ko'rsatadi.
Bu misolda adjacency matrix (adjansiya matrisa) yordamida graf yaratilgan. Undirected graph (bir tomonlama graf) uchun, yon birligi qo'shishda ikkita tugun o'rtasida birlashmasini ko'rsatish uchun ikkita joyda alohida yon birligi qo'shilgan.
Bu bilan siz C++ tilida qo'shma matrisa usullaridan foydalanib grafni ifodalashni boshlay olasiz. Kiritilgan yordam va kodlar asosida graf yaratish va uning bog'liqlik matrisasini ko'rish mumkin bo'ladi.
Masalalar
Tabiatan, grafning qo'shnilik matrisasini tuzish uchun berilgan ma'lumotlarni nazorat qilish lozim. Qo'shnilik matrisasining qaysi ko'rinishda tuzilishi (adjacency matrix, incidence matrix va hokazo) kerakli. Ammo umuman olganda, bir grafda yonlar (edges) haqida berilgan ma'lumotlar asosida qo'shnilik matrisasi tuzish mumkin. Misol uchun agar berilgan ma'lumotlar tugunlarning (vertices) soni va ularning yonlari bo'lsa, adjacency matrix (adjansiya matrisa) ishlatilishi mumkin.
Mana shu ma'lumotlar asosida tugunlar soni 5 va yonlar: (0, 1), (0, 2), (1, 3), (2, 4) bo'lsa, bu ma'lumotlarga ko'ra adjacency matrix ni C++ tilida tuzish mumkin
C++ da dastur kodi:
#include
#include
using namespace std;
int main() {
const int vertexCount = 5; // Tugunlar soni
int adjacencyMatrix[vertexCount][vertexCount] = {0}; // Adjansiya matrisa
// Yonlarni ko'rsatish
vector
> edges = {{0, 1}, {0, 2}, {1, 3}, {2, 4}};
// Adjacency matrix (adjansiya matrisa) tuzish
for (const auto& edge : edges) {
int fromVertex = edge.first;
int toVertex = edge.second;
adjacencyMatrix[fromVertex][toVertex] = 1;
// Agar undirected graf bo'lsa
adjacencyMatrix[toVertex][fromVertex] = 1;
}
// Matrisani ko'rsatish
cout << "Adjacency Matrix:" << endl;
for (int i = 0; i < vertexCount; ++i) {
for (int j = 0; j < vertexCount; ++j) {
cout << adjacencyMatrix[i][j] << " ";
}
cout << endl;
}
return 0;
}
XULOSA:
Xulosam shuki qo'shma matrisa usuli grafiklarni osonlik va samaradorlik bilan ifodalash, algoritmalar uchun ma'lumotlarni amaliy implementatsiyasini osonlashtiradi va grafiklar haqida tahlillar va hodisalar uchun asosiy ma'lumotlar manbasi bo'ladi.
Graflarni tasvirlash usullari va qo'shma matrisa usuli, grafiklarni ifodalash va ulardan foydalanishda qulaylik va samaradorlikni ta'minlaydi. Har bir usul o'zining o'zaro afzalliklari bilan aloqador maqsadlar uchun foydalanilishi mumkin.
Adabiyotlar
^ Sedgewick, Robert (1 sentyabr 1998 yil). Algorithms In C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 (3 nashr). Pearson ta'limi. ISBN 978-81-317-1291-7.
^ Sedgewick, R. (1978). "Implementing Quicksort programs". Kom. ACM. 21 (10): 847–857. doi:10.1145/359619.359631.
^ "SELECTION SORT (Java, C++) - Algorithms and Data Structures". www.algolist.net.
|
| |
