94
f)
g)
7-§. Grafda oʻtish algoritmlari
Graflar bilan ishlashda barcha asosiy amallar (masalan, grafni bitta
koʻrinishda ikkinchisiga oʻtkazish, bosib chiqarish yoki grafni chizish)
uning tizimli oʻtishini, ya‘ni grafning har bir uchiga va har bir qirrasiga
tashrif buyurishni nazarda tutadi. Agar labirintni graf koʻrinishida
namoyish etsak, u yerda qirralar oʻtish joylari,
uchlar esa qirralarning
kesishish nuqtalari boʻlsa, u holda grafni bosib oʻtish uchun har qanday
toʻgʻri algoritm ixtiyoriy ravishda labirintidan chiqish yoʻlini topishi
kerak. Ushbu algoritmlarning eng mashhurlari grafda oʻtish boʻyi
boʻyicha qidiruv (DFS) va oʻtish eni boʻyicha qidiruv (BFS) algoritmlari
boʻlib, ular qoʻllaniladigan muammolarni hal qilish uchun koʻplab
boshqa algoritmlar uchun asos boʻlib xizmat qiladi.
Graflar boʻylab harakatlanishning asosiy gʻoyasi
shundaki, har bir
uchni birinchi marta tashrif buyurganingizda
belgilang va barcha
qirralari koʻrib chiqilmagan uchlar haqidagi ma‘lumotlarni saqlang.
Qadimgi Yunoniston afsonalarida Tesey labirint atrofida yurish uchun
Ariadna
bergan ipdan foydalangan, qarichlab tosh yoki maydalangan
toshlar bilan bosib oʻtgan yoʻlini belgilab qoʻygan, sanab oʻtilgan turlar
grafni bosib oʻtish uchun ishlatilgan. Grafni bosib oʻtish jarayonida har
bir uch uchta holatdan birida boʻladi:
1) ochilmagan - uchning dastlabki holati;
2)
ochiq - uch topilgan, ammo unga tushgan qirralar koʻrib
chiqilmagan;
95
3) ishlov berilgan (belgilangan) - ushbu uchga tushgan barcha
qirralarga tashrif buyuriladi.
Grafning har bir uchi ketma-ket ushbu holatlarning barchasini qabul
qilishi aniq. Dastlab, faqat bitta uch ochiq boʻladi, ya‘ni
grafni bosib
oʻtish ushbu uchdan boshlanadi.
