Genişliyinə görə axtarış alqoritmləri (BFS)

8.1 BFS alqoritminin işləmə prinsipləri

Eninə axtarış (Breadth-First Search, BFS) — bu, qrafda keçid və ya axtarış alqoritmidir ki, başlanğıc zirvədən başlayır və hər bir səviyyədəki bütün qonşu zirvələri növbəti səviyyəyə keçməmişdən əvvəl tədqiq edir.

Alqoritmin addımları:

1. Seçilmiş başlanğıc zirvədən başlayırıq və onu növbəyə əlavə edirik.
2. Növbə boş olmayana qədər aşağıdakı əməliyyatları icra edirik:
   • Zirvəni növbənin başından çıxarırıq və onu ziyarət edilmiş kimi qeyd edirik.
   • Ziyarət edilməmiş hər bir qonşu zirvə üçün onu növbəyə əlavə edirik.
3. Addım 2-ni təkrar edirik, ta ki başlanğıc zirvədən əlçatan olan bütün zirvələr ziyarət edilənədək.

Vizualizasiya:

Zaman mürəkkəbliyi:

O(V + E), burada V — zirvələrin sayı, E — kənarların sayı.

Qrafın hər bir düyünü və hər bir kənarı bir dəfə ziyarət edilir.

Məkan mürəkkəbliyi:

O(V), çünki zirvələrin saxlanması üçün növbə, həmçinin vəziyyətin saxlanması üçün massivlər istifadə olunur (ziyarət edilmiş zirvələr).

8.2 BFS-in növbədən istifadə edərək reallaşdırılması

Genişliyə görə keçid növbə kimi məlumat strukturundan istifadə edərək yaxşı reallaşdırılır.

Növbədən istifadə edərək BFS-in reallaşdırılması:

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
            
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Uzanın emalı
            
            for neighbor in graph[vertex]:
                if neighbor not in visited:
                    queue.append(neighbor)
            
# İstifadə nümunəsi:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
bfs(graph, 'A')

8.3 İkitərəfli eninə axtarış

BFS tez-tez oyunlarda istifadə olunur, harada ki, mürəkkəb bir landşaftda iki nöqtə arasında ən qısa yolu tapmaq lazımdır. Belə bir tapşırıq asanlıqla qrafda iki təpə arasında yol axtarışı məsələsinə çevrilir. Bu qrafın kənarları xəritədəki keçilə bilən bütün yollar olur.

Amma yolu daha tez tapmaq üçün onu adətən iki istiqamətdən axtarırlar. Bu məqsədlə ikitərəfli BFS tətbiq edilir.

İş prinsipi

İkitərəfli eninə axtarış (Bidirectional BFS) — BFS alqoritminin optimallaşdırılmış versiyasıdır və o qrafın iki paralel axtarışını həyata keçirir: biri başlanan təpədən, digəri isə hədəf təpədən. Axtarışlar iki axtarış bir-birinə rast gələnə qədər davam edir ki, bu da klassik BFS ilə müqayisədə yoxlanılan təpələrin və kənarların sayını əhəmiyyətli dərəcədə azaldır.

Alqoritmin addımları:

• İki növbənin ilkinləşdirilməsi: biri başlanan təpədən axtarış üçün, digəri isə hədəfdən.
• Hər iki istiqamətdə ziyarət edilmiş təpələrin izlənilməsi üçün iki ziyarət edilmiş təpələr çoxluğunun ilkinləşdirilməsi.
• Qrafın iki növbəsindən növbə ilə axtarış həyata keçirmək.
• Hər addımda ziyarət edilmiş təpələr çoxluqlarının kəsişib-kəsişməməsi yoxlanılır. Əgər kəsişmə tapılıbsa, yol mövcuddur.
• Proses hər hansı bir kəsişən node tapılana qədər və ya növbələr boşalana qədər davam edir.

Zaman mürəkkəbliyi

Ən yaxşı halda: O(2 * (V + E)) = O(V + E), burada V — təpələrin sayı, E — kənarların sayı.

İkitərəfli BFS adətən böyük qraflarda tək keçidli BFS ilə müqayisədə daha az sayda təpələri əhatə edir.

Məkan mürəkkəbliyi:

O(V) iki növbəni və iki ziyarət edilmiş təpələr çoxluğunu saxlamaq üçün.

İkitərəfli BFS-in həyata keçirilmə nümunəsi

Nümunə çox uzundur — alqoritm bir istiqamətli axtarışdan üç dəfə daha uzun — buna görə onu gətirməyəcəyəm. Nə vaxt ki, sizə həqiqətən lazım olacaq, siz onun özünü yazmaq vəziyyətində olacaqsınız.

8.4 BFS istifadə edilən məsələlərin nümunələri

BFS istifadə edilən klassik məsələlərin nümunələri:

1. Yönləndirilməmiş qrafda ən qısa yolun axtarışı:

BFS başlanğıc zirvəsindən hədəf zirvəsinə qədər yönləndirilməmiş qrafda ən qısa yolu (minimum kənarların sayını) tapmaq üçün istifadə olunur.

Tətbiq:

• Naviqasiya sistemlərində nöqtələr arasında ən qısa yolun tapılması üçün.
• Şəbəkə analizində məlumat ötürülməsi üçün ən qısa yolun tapılması üçün.

2. Qrafın əlaqəliliyinin yoxlanılması:

Qrafın əlaqəli olub-olmadığını yoxlamaq, yəni hər hansı iki zirvə arasında yolun olub-olmadığını göstərmək.

Tətbiq:

• Şəbəkə analizində şəbəkənin əlaqəliliyinin yoxlanılması üçün.
• Sosial şəbəkələrin analizində istifadəçi qruplarının əlaqəliliyinin yoxlanılması üçün.

3. Labirintlərin yaradılması:

Xüsusi xüsusiyyətləri olan təsadüfi labirintlərin yaradılması üçün BFS-in istifadəsi.

Tətbiq:

• Oyun tətbiqlərində labirintlərin yaradılması üçün.
• Robototexnikada naviqasiya alqoritmlərinin test edilməsi üçün.

4. Ağaclarda eninə axtarış:

Ağacları keçmək üçün BFS istifadə olunur, belə ki, ağacın hər səviyyəsində əməliyyatlar (məsələn, hər səviyyədə bütün qovşaqların çap edilməsi) həyata keçirilir.

Tətbiq:

• Məlumatların səviyyələr üzrə göstərilməsini tələb edən məlumat vizuallaşdırma məsələlərində.
• Hierarxiyanın hər səviyyəsində əməliyyatların yerinə yetirilməsini tələb edən planlaşdırma məsələlərində.

5. Qrafın iki tərəfliliyinin yoxlanılması:

Qrafın iki tərəfli olub-olmadığını yoxlamaq, yəni onun zirvələrini iki çoxluğa bölmək mümkün olub-olmadığını yoxlamaq (belə ki, kənarlar yalnız müxtəlif çoxluqlardakı zirvələr arasında mövcuddur).

Tətbiq:

• Qraf nəzəriyyəsində qrafın iki tərəfliliyinin yoxlanılması üçün.
• Qrafın iki rənglə boyanmasının mümkün olub-olmadığını yoxlamaq üçün qraf boyama məsələlərində.