Dərinlik üzrə axtarış (DFS) alqoritmləri

7.1 DFS alqoritminin işləmə prinsipləri

Dərinliyinə doğru axtarış (Depth-First Search, DFS) — bu, qrafın dolaşma və ya axtarış alqoritmidir. Əsas başlanğıc zirvəsindən başlayır və zirvələrin ziyarət olunmamış qonşuları qalmayana qədər qrafda irəliləyir, daha sonra geriyə qayıdır və prosesə digər zirvələrdən davam edir.

Alqoritmin addımları:

1. Seçilmiş başlanğıc zirvəsindən başlayırıq və onu ziyarət olunmuş kimi işarələyirik.
2. Ziyarət olunmamış ilk qonşu zirvəni araşdırırıq.
3. Bu qonşu zirvə üçün 1-ci və 2-ci addımları təkrar edirik.
4. Əgər cari zirvənin bütün qonşuları ziyarət olunubsa, geriyə qayıdırıq (backtrack) əvvəlki zirvəyə və prosesi davam etdiririk.
5. Proses, başlanğıc zirvədən əlçatan olan bütün zirvələr ziyarət olunana qədər davam edir.

Vizualizasiya:

DFS-in vaxt və yaddaş mürəkkəbliyi:

Vaxt 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 olunur.

Yaddaş mürəkkəbliyi:

O(V), çünki çağırış stack-i və ya zirvələri saxlamaq üçün açıq stack istifadə olunur, həmçinin vəziyyəti saxlamaq üçün massivlər (ziyaret olunmuş zirvələr) istifadə edilir.

7.2 Rekursiyadan istifadə etməklə DFS-in tətbiqi

Gəlin əvvəlcə rekursiyadan istifadə etməklə DFS-i tətbiq edək — kod gözəl və yığcam olacaq.

DFS-in rekursiv tətbiqi:

def dfs_recursive(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)  # Node emalı
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# İstifadə nümunəsi:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_recursive(graph, 'A')

7.3 Stakdan istifadə edərək DFS-in reallaşdırılması

Rekursiyasız kod bir az daha uzun olacaq, çünki əlavə olaraq ziyarət edilmiş təpələrin siyahısını saxlamağımız lazımdır.

Stakdan istifadə edərək iterativ DFS reallaşdırılması:

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
        
    while stack:
        vertex = stack.pop()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)  # Uzanın emalı
        
            for neighbor in reversed(graph[vertex]):  # Doğru keçid sırası üçün geriyə doğru sıralama
                if neighbor not in visited:
                    stack.append(neighbor)
        
# İstifadə nümunəsi:
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B'],
    'F': ['C']
}
dfs_iterative(graph, 'A')

7.4 DFS-dən istifadə ilə həll olunan məsələlərin nümunələri

DFS-dən istifadə ilə həll olunan klassik məsələlərin nümunələri:

1. Labirintdə yol tapmaq:

Başlanğıc nöqtədən son nöqtəyə qədər labirintdə yol tapmaq üçün istifadə edilir.

Tətbiq sahəsi:

Video oyunlarında və robot texnikasında labirintlərdə və mürəkkəb məkanlarda naviqasiya üçün.

2. Qrafın əlaqəliliyini yoxlamaq:

Qrafın əlaqəli olub-olmadığını yoxlamaq (istənilən iki zirvə arasında yolun olub-olmaması).

Tətbiq sahəsi:

Şəbəkə təhlilində şəbəkənin əlaqəliliyini yoxlamaq üçün.

3. Topoloji sıralama:

Yönləndirilməmiş dövrü olmayan qrafın (DAG) zirvələrini elə sıralamaq üçün istifadə edilir ki, istənilən (u, v) kənarında zirvə u zirvədən v əvvəl gəlir.

Tətbiq sahəsi:

Kompilyatorlarda asılılıqların və vəzifələrin sıralanması üçün.

4. Qrafda dövrələrin aşkarlanması:

Qrafın dövrə ehtiva edib-etmədiyini yoxlama.

Tətbiq sahəsi:

Asılılıq analizində dövrəvi asılılıqları aşkarlamaq üçün.

5. Labirintlərin yaradılması:

Rastgəl labirintlər yaratmaq üçün DFS-nin istifadəsi.

Tətbiq sahəsi:

Oyun və əyləncə tətbiqlərində labirintlərin yaradılması üçün.