O'zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari

O'ZBEKISTON RESPUBLIKASI AXBOROT
TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH
VAZIRLIGI MUHAMMAD AL-XORAZMIY
NOMIDAGI TOSHKENT AXBOROT
TEXNOLOGIYALARI UNIVERSITETI SAMARQAND
FILIALI
Komputer injinering yo’nalishi 3-kurs 20-02-guruh
talabasi Azizov Mironshohning Ma'lumotlar
tuzulmasi va algorimlar fanidan bajargan
MUSTAQIL ISHI


Bajardi : Azizov M
Tekshirdi: Isroilov Sh
Samarqand-2022
Mustaqil ish – 2

Tubiga qarab qidiruv (Depth-first search, DFS) algoritmi

Depth first search algoritmi

Depth first search (DFS) algoritmi oson klassik graph algoritmlaridan biri bo’lib, u rekursiya ichida graph’dagi barcha vertex’larni tekshirib chiqishga yordam beradi. Aslida biz bu algoritmdan binary search tree‘dagi barcha ma’lumotlarni ko’rib chiqish uchun foydalanib, traverse() funksiyasini yozganmiz.
Depth first search algoritmining klassik deyilishiga sabab, qadimda undan labirintdan chiqish yo’lini topish uchun foydalanishgan. Labirintning boshlanish joyida g’altak – koptok qilib o’ralgan ipni ochib, yo’lni topishga kirishishgan. Berk ko’chaga kirib qolishganda, ip bo’yicha orqaga qaytib, kirilmagan yo’ldan davom ettirishgan. Shu tariqa ip orqali yurilgan yo’llarga qayta kirmaslik uchun ularni belgilab borishgan. Ip orqali yo’l topishni Trémaux maze exploration deb ham ataladi.

Labirint yechishni dasturda modellashtirish uchun labirintni graph’ga aylantiramiz. Bunda labirintning yo’llari edge’lar, chorrahalar vertex’lar bo’ladi.
Labirintni graph’ga aylantirish.
Avvaldan aytib o’tish kerakki, Depth first search algoritmi labirintdan tez chiqib ketish uchun eng yaxshi yechim emas, u qisqa yo’lni topmaydi. Algoritm shunchaki «boshi oqqan ko’chaga» kirib chiqib, yo’l bor yo’qligini tekshiradi.
Kompyuterchasiga tushuntirganda, vertex’ning edge’lari bor yo’qligini tekshiradi, bor bo’lsa, har bir edge’dagi vertex’dan tekshiruvni davom ettiradi.

Algoritmning ishlash tartibi (vizualizatsiya)

Quyidagi graphning barcha vertex’larini tekshirib, qiymatlarini yig’ib chiqishimiz kerak bo’lsin.

DFS algoritmini A vertex’dan boshlaymiz. A topildi, uni «o’qilgan» qilib belgilaymiz (marked). Rekursiv funksiya stack tartibida ishlagani uchun, stack’ning tepasida A turipti, ya’ni funksiya A vertex uchun ishlamoqda.

A vertex bog’langan boshqa vertex’larni tekshiramiz. U B va G ga ulangan. Tekshiruvni B dan davom ettiramiz. Nima uchun B’dan? Aslida DFS algoritmi uchun B yoki G dan davom ettirishning ahamiyati yo’q. Esingizda bo’lsa graph uchun api yozganimizda, biz edge’larni Set ichida saqlagandik. Edge’ni o’qib olishda ham Set beradigan edge’lar bo’yicha DFS ishni davom ettiradi.

B stack’ning yuqorisida. Algoritm B’ga bog’langan tekshirilmagan vertex’larini tekshiradi. Ular C va G. C dan davom ettiradi.

C ga bog’langan tekshirilmagan vertex’lari yo’q. Stack’dagi C funksiya ishini to’xtatadi, demak C stackdan o’chiriladi.

Endi stack’ning yuqorisida B turipti. B ga bog’langan kirilmagan vertex – G.
G stack’ga qo’shiladi.

G stack’ning yuqorisida. G ga bog’langan kirilmagan bitta vertex bor – E.

E da kirilmagan ikki vertex bor: J va K. J dan davom ettiradi.

J ning kirilmagan ikki vertex bor: F va D. D dan davom ettiradi.

D ning kirilmagan bitta vertex bor: K. K dan davom ettiradi.

K ga bog’langan kirilmagan vertex yo’q. K stackdan chiqariladi – rekursiyadagi K funksiya ishini tugatadi.

D ga bog’langan kirilmagan vertex yo’q. D stackdan chiqariladi – rekursiyadagi D funksiya ishini tugatadi.

J stack’ning yuqorisida. J ga bog’langan kirilmagan F vertex bor. F dan davom ettiradi.

F ga bog’langan kirilmagan vertex’lar yo’q. F stackdan chiqariladi – rekursiyadagi F funksiya ishini tugatadi.

J ga bog’lagan kirilmagan vertex’lar yo’q. J stackdan chiqariladi.

E ga bog’langan kirilmagan vertex’lar yo’q. E stackdan chiqariladi.

G ga bog’langan kirilmagan vertex’lar yo’q. G stackdan chiqariladi.

B ga bog’langan kirilmagan vertex’lar yo’q. B stackdan chiqariladi.

A ga bog’langan kirilmagan vertex’lar yo’q. A stackdan chiqariladi.

DFS algoritmi ishini tugatdi.

Depth first search algoritmini kodda ifodalash

Graph yasash uchun bizda allaqachon Graph API bor. Kirilgan vertex’larni marked[] da belgilab, edgeTo[] ga esa vertex’ga qaysi vertex’dan kelinganini qo’shib boramiz. Shunda edgeTo[w] == v degani, w vertex’ga v vertex’dan kelinganini bildiradi. edgeTo dagi ma’lumotlar asosida biz bir vertex’dan ikkinchi vertex’ga yo’lni topishimiz mumkin.
Quyidagi funksiya deep first search algoritmi asosida berilgan vertex’ga bevosita va bilvosita bog’langan vertex’lar ro’yhatini qaytaradi:
const AdjacencyListGraph = talab ('./adjacency-list-graph')

/**
* s ga ulangan barcha uchlarini toping (va mos keladigan yo'l).

* @param {Array} grafigi
* @param {Ob'ekt} s
*/
findBog'lanish funktsiyasi (grafik, s) {
const belgilangan = Massiv (grafik.uzunlik).map(() => noto'g'ri)
const edgeTo = Massiv (graph.length).map(() => null)
const topildi = []

// Rekursiv yordamchi funksiyani ishga tushiring

dfsHelper(lar)

funktsiya dfsHelper(vertex) {

// Cho'qqini tashrif buyurilgan deb belgilang
belgilangan[vertex] = rost

// Joriy cho'qqining qirralarini takrorlang

uchun (grafikning cheti [cho'qqi]) {
// Kenarga hali tashrif buyurilmaganligini tekshiring
agar (!belgilangan[qirra]) {
// Joriy chekka uchun funksiyani qayta ishga tushirish
dfsHelper(chekka)

// Yo'lni ushlab turish uchun chekka ro'yxatiga vertex qo'shing

edgeTo[chekka] = vertex

// Bog'langan uchlarini qo'shish

topildi.surish(chekka)
}
}
}

// Bog'langan cho'qqilarni qaytaring

qaytish topildi
}

/**
* FOYDALANISH

*/

// 10 ta burchakli grafik yarating

const grafigi = yangi AdjacencyListGraph(10)

// Qirralarni qo'shish

graph.addEdge(0,1)
graph.addEdge(0,2)
graph.addEdge(0,6)
graph.addEdge(0,5)
graph.addEdge(6,4)
graph.addEdge(4,3)
graph.addEdge(4,5)
graph.addEdge(3,5)
// Barcha bog'langan 0 cho'qqisini oling
console.log(findConnections(graph.get(), 0))
Ikki vertex orasidagi yo’lni topish Graph APIda realizatsiya qilingan:
https://github.com/Webmaxor/leetcode-solutions/blob/master/algorithms/graphs/adjacency-list-graph.js

Azizov Mironshoh