Tarkibga o'tish

BFS va DFS

Graf yaratilgandan keyin tabiiy savol paydo bo'ladi: uning ichida qanday harakat qilinadi? Bitta vertex berilganda, undan yetib borish mumkin bo'lgan barcha boshqa vertexlarni qanday topish mumkin? Qaysi vertex boshqasidan yaqinroq? Cycle bormi? Bu savollarning hammasi traversal — grafni sistematik ko'rib chiqish — masalasiga qaytadi.

Array yoki linked listda traversal sodda: boshidan oxirigacha ket. Grafda bunday aniq yo'nalish yo'q. Bitta vertexdan bir nechta qo'shni borishi, ba'zi yo'llar kesishishi, ayrim vertexlarga bir nechta yo'l orqali yetib borish mumkin. Ustiga-ustak, cycle mavjud bo'lsa cheksiz aylanib qolish xavfi bor.

Bu muammoni hal qiluvchi ikki fundamental yondashuv bor: BFS va DFS. Ularning ikkalasi ham barcha reachable vertexlarni bir marta ko'radi, lekin qaysi tartibda ko'rishida printsipial farq bor. Bu farq qaysi masalalarda qaysi biri to'g'ri yechim berishini belgilaydi.

BFS: qatlamma-qatlam yurish

Asosiy g'oya

BFS (breadth-first search) boshlang'ich vertexdan eng yaqin qo'shnilarni avval, keyin ularning qo'shnilarini, undan keyin yanada uzoqroqlarini qayta ishlaydi.

        A          Qatlam 0: A
      /   \         Qatlam 1: B, C
     B     C        Qatlam 2: D, E, F
    / \     \
   D   E     F

Bu xuddi toshni suvga tashlagandek tarqalish: markazdan tashqariga to'lqin bo'lib ketadi. BFS har qatlamni to'liq tugallagach keyingisiga o'tadi.

Buni amalga oshirish uchun queue (navbat) kerak. Queue FIFO — oldin kirgani oldin chiqadi. BFS quyidagicha ishlaydi:

  1. Boshlang'ich vertex queuega solinadi va visited deb belgilanadi.
  2. Queue bo'sh bo'lmagunicha: bitta vertex chiqariladi, uning hali ko'rilmagan barcha qo'shnilari visited belgilanib queuega solinadi.
  3. Queue bo'shaganda — barcha reachable vertexlar ko'rilgan.
FUNCTION BFS(graph, start)
    IF start grafda mavjud bo'lmasa
        RETURN

    queue    = bo'sh queue
    visited  = bo'sh set

    visited ga start ni qo'sh
    queue.ENQUEUE(start)

    WHILE queue bo'sh emas
        current = queue.DEQUEUE()
        PROCESS current

        FOR har bir neighbor graph.adjacency[current] ichida
            IF neighbor visited ichida bo'lmasa
                visited ga neighbor ni qo'sh
                queue.ENQUEUE(neighbor)

Nega visited enqueue paytida qo'yiladi?

Bir vertexga bir nechta yo'l bo'lsa, uni queuega ikki marta solib qo'yish mumkin:

    A
   / \
  B   C
   \ /
    D

B ham, C ham Dni qo'shni sifatida ko'radi. Agar visited faqat dequeue paytida qo'yilsa, D ikki marta queuega tushadi va ikki marta qayta ishlanadi. Enqueue paytida qo'yish buni oldini oladi: birinchi marta qo'shilganda visited bo'lib qoladi, ikkinchi urinish tekshiruvdan o'tolmaydi.

BFS va eng qisqa yo'l

BFS og'irliksiz grafda boshlang'ich vertexdan barcha boshqa vertexlargacha eng kam qirrali pathni topadi. Sababi oddiy: BFS avval 1 ta qirra naridagilarni, keyin 2 ta, keyin 3 ta qirra naridagilarni qayta ishlaydi. Biror vertex birinchi marta ko'rilganda — u eng qisqa yo'l orqali topilgan. Undan keyinroq topilishi kamroq qirra bilan topilganligi mumkin emas.

Yo'lning o'zini tiklash uchun har vertexning "kimdan kelindi" ma'lumotini saqlab, maqsaddan startgacha orqaga yurish kerak:

FUNCTION BFS_SHORTEST_PATH(graph, start, target)
    queue   = bo'sh queue
    visited = bo'sh set
    parent  = bo'sh map        // vertex → kimdan ochildi

    visited ga start ni qo'sh
    queue.ENQUEUE(start)
    parent[start] = NULL

    WHILE queue bo'sh emas
        current = queue.DEQUEUE()

        IF current = target
            BREAK

        FOR har bir neighbor graph.adjacency[current] ichida
            IF neighbor visited ichida bo'lmasa
                visited ga neighbor ni qo'sh
                parent[neighbor] = current
                queue.ENQUEUE(neighbor)

    IF target visited ichida bo'lmasa
        RETURN "yo'l yo'q"

    path = bo'sh list
    v = target
    WHILE v ≠ NULL
        path ga v ni qo'sh
        v = parent[v]

    RETURN path ni teskari tartibda

parent map har vertexning qaysi vertexdan ochilganini saqlaydi. Targetdan startgacha orqaga yurish to'liq pathni beradi.

Qatlamlarni alohida qayta ishlash

Ba'zan har qatlam — har masofa darajasi — alohida qayta ishlanishi kerak. Masalan, "startdan aynan k qirra naridagi barcha vertexlar" yoki "har qatlamda birorta ish bajarish" kabi vazifalar:

FUNCTION BFS_BY_LEVEL(graph, start)
    queue   = [start]
    visited = {start}
    level   = 0

    WHILE queue bo'sh emas
        level_size = queue hajmi
        PRINT "Qatlam " + level + ":"

        FOR i = 0 DAN level_size - 1 GACHA
            current = queue.DEQUEUE()
            PROCESS current

            FOR har bir neighbor graph.adjacency[current] ichida
                IF neighbor visited ichida bo'lmasa
                    visited ga neighbor ni qo'sh
                    queue.ENQUEUE(neighbor)

        level = level + 1

Har iteratsiya boshida level_size o'sha qatlamdagi elementlar sonini saqlaydi. Shu miqdorcha dequeue qilinadi — faqat hozirgi qatlam. Keyingisi keyingi iteratsiyada ko'riladi.

Multi-source BFS

Ayrim masalalarda bitta emas, bir nechta boshlang'ich vertexdan bir vaqtda traversal boshlanadi. Masalan, "barcha rotten apelsinlar bir vaqtda chirishni tarqatadi" yoki "bir nechta manba bir vaqtda yaqin hududlarni kashf qiladi" kabi holat:

FUNCTION BFS_MULTI_SOURCE(graph, sources)
    queue   = bo'sh queue
    visited = bo'sh set

    FOR har bir source sources ichida
        visited ga source ni qo'sh
        queue.ENQUEUE(source)

    WHILE queue bo'sh emas
        current = queue.DEQUEUE()
        PROCESS current

        FOR har bir neighbor graph.adjacency[current] ichida
            IF neighbor visited ichida bo'lmasa
                visited ga neighbor ni qo'sh
                queue.ENQUEUE(neighbor)

Bu oddiy BFS bilan bir xil — faqat bitta boshlang'ich o'rniga bir nechta manba bir vaqtda queuega solinadi. Natijada barcha manbalardan teng ravishda, tenglashtirilgan holda tarqalib chiqiladi.

BFS murakkabligi

Adjacency list bilan:

  • Vaqt: O(V + E) — har vertex bir marta queuedan chiqadi, har edge adjacency listda bir marta ko'riladi.
  • Xotira: O(V) — visited set va queue birga maksimum O(V) element saqlaydi.

Adjacency matrix bilan har vertex uchun butun qatorni tekshirish O(V²) vaqt talab qiladi.

Xotira nuqtai nazaridan: keng va sershox grafda BFS queuesi katta bo'lishi mumkin. Bitta boshlang'ichdan reachable bo'lgan barcha vertexlar bir vaqtda queueda bo'lmasligi kafolatlanmaydi — worst case barcha vertexlar queueda turishi mumkin.

DFS: chuqurlikka sho'ng'ish

Asosiy g'oya

DFS (depth-first search) bir yo'l bo'ylab imkon qadar chuqur boradi, to'siqqa yetgach (visited vertex yoki yo'l yo'q) orqaga qaytib boshqa yo'lni tekshiradi.

        A          DFS (bir mumkin tartibi):
      /   \         A → B → D → (orqaga) → E → (orqaga) → (orqaga) → C → F
     B     C
    / \     \
   D   E     F

Orqaga qaytish rekursiya call stack yordamida avtomatik amalga oshiriladi. DFS rekursiya yoki explicit stack bilan yoziladi.

Rekursiv DFS

FUNCTION DFS(graph, current, visited)
    visited ga current ni qo'sh
    PROCESS current

    FOR har bir neighbor graph.adjacency[current] ichida
        IF neighbor visited ichida bo'lmasa
            DFS(graph, neighbor, visited)

Rekursiv DFS toza va o'qilishi qulay. Har rekursiv chaqiruv joriy vertexni va "qaerdan kelindi" ma'lumotini call stackda saqlaydi. Graf juda chuqur bo'lsa — masalan, million vertexli zanjir shaklidagi graf — call stack to'lishi (stack overflow) mumkin.

Iterativ DFS

FUNCTION DFS_ITERATIVE(graph, start)
    stack   = bo'sh stack
    visited = bo'sh set

    stack.PUSH(start)

    WHILE stack bo'sh emas
        current = stack.POP()

        IF current visited ichida bo'lsa
            CONTINUE

        visited ga current ni qo'sh
        PROCESS current

        FOR har bir neighbor graph.adjacency[current] ichida
            IF neighbor visited ichida bo'lmasa
                stack.PUSH(neighbor)

Iterativ DFS rekursivdan biroz farq qiladi: visited pop paytida belgilanadi, push paytida emas. Bu sababli bir vertex bir nechta marta stackga tushishi mumkin — CONTINUE bu holatni nazorat qiladi.

Neighborlar stackga teskari tartibda solinsa traversal tartibi rekursiv DFS bilan yaqinlashadi, lekin bu detalga ortiqcha tayanmaslik kerak. Rekursiv va iterativ DFS neighborlar tartibiga qarab turli, ammo ikkalasi ham to'g'ri traversal beradi.

Preorder va postorder

DFS traversalida ikki muhim nuqta mavjud:

FUNCTION DFS(graph, current, visited)
    visited ga current ni qo'sh

    PROCESS current         // <-- PREORDER: vertex ko'rildi, qo'shnilari hali yo'q

    FOR har bir neighbor graph.adjacency[current] ichida
        IF neighbor visited ichida bo'lmasa
            DFS(graph, neighbor, visited)

    PROCESS current         // <-- POSTORDER: bu vertex va undan reachable barcha vertexlar ko'rildi

Preorder — vertex ko'rilganda darhol ishlov beriladi. Ko'p traversal masalalarida, path qurishda ishlatiladi.

Postorder — vertex va uning orqali yetish mumkin bo'lgan barcha vertexlar qayta ishlangandan keyin ishlov beriladi. Topological sort va cycle detection uchun postorder muhim.

Postorder DFSda "finishing time" — vertex o'z subtreesini tugatganda — muhim invariant. Bu directed grafda strongly connected components topishda va topological sortda ishlatiladi.

DFS va cycle detection

Undirected grafda:

DFS vaqtida hozirgi vertexdan "kelgan" ota vertex bo'lmagan boshqa visited vertex ko'rilsa — cycle mavjud:

FUNCTION HAS_CYCLE_UNDIRECTED(graph, current, visited, parent)
    visited ga current ni qo'sh

    FOR har bir neighbor graph.adjacency[current] ichida
        IF neighbor visited ichida bo'lmasa
            IF HAS_CYCLE_UNDIRECTED(graph, neighbor, visited, current)
                RETURN TRUE
        ELSE IF neighbor ≠ parent
            RETURN TRUE      // ota bo'lmagan visited qo'shni = cycle

    RETURN FALSE

Nega neighbor ≠ parent tekshiruvi kerak? Undirected grafda A—B qirra mavjud bo'lsa, Adan Bga borganda Bning qo'shnilari orasida A ham bor. Bu bir xil qirra bo'ylab teskari qaytish — cycle emas. Ammo Adan Bga borib, Bdan Adan boshqa yo'l orqali Aga qaytish — haqiqiy cycle.

Directed grafda:

Directed grafda ota-bola farqi etarli emas. "Hozirgi DFS yo'li bo'ylab" — ya'ni recursion stackdagi — vertex ko'rilsa, cycle bor:

FUNCTION HAS_CYCLE_DIRECTED(graph, current, visited, in_stack)
    visited ga current ni qo'sh
    in_stack ga current ni qo'sh

    FOR har bir neighbor graph.adjacency[current] ichida
        IF neighbor visited ichida bo'lmasa
            IF HAS_CYCLE_DIRECTED(graph, neighbor, visited, in_stack)
                RETURN TRUE
        ELSE IF neighbor in_stack ichida bo'lsa
            RETURN TRUE      // hozirgi DFS yo'lidagi vertex = cycle

    in_stack dan current ni olib tashla
    RETURN FALSE

in_stack — hozirgi recursion stackdagi vertexlar to'plami. Vertex o'z subtreesini tugallagach in_stackdan chiqariladi. Shunday qilib, boshqa yo'l orqali topilgan allaqachon ko'rilgan vertex cycle deb hisoblanmaydi — faqat hozirgi aktiv yo'ldagi vertex.

DFS va topological sort

DAG (directed acyclic graph) vertexlarini barcha u → v edge'lar uchun u vdan oldin turadigan tartibda joylashtirish topological sort deyiladi. Kurs prerequesite'lari yoki build dependency tartibi shu muammoning real ko'rinishi.

DFS postorder bilan:

FUNCTION TOPOLOGICAL_SORT(graph)
    visited = bo'sh set
    result  = bo'sh stack

    FUNCTION DFS_TOPO(current)
        visited ga current ni qo'sh

        FOR har bir neighbor graph.adjacency[current] ichida
            IF neighbor visited ichida bo'lmasa
                DFS_TOPO(neighbor)

        result.PUSH(current)   // postorder: barcha qo'shnisi ko'rilgach qo'shiladi

    FOR har bir vertex graph ichida
        IF vertex visited ichida bo'lmasa
            DFS_TOPO(vertex)

    RETURN result ni teskari tartibda

Nima uchun postorder ishlaydi? Vertex resultga solinishi uning barcha reachable vertexlari allaqachon qo'shilganidan keyin sodir bo'ladi. Shuning uchun resultni teskari o'qish barcha dependency'lardan oldin ularning "foydalanuvchi"larini beradi.

DFS murakkabligi

Adjacency list bilan:

  • Vaqt: O(V + E) — har vertex bir marta ko'riladi, har edge bir marta tekshiriladi.
  • Xotira: O(V) — visited set va call stack yoki explicit stack.

Call stack chuqurligi grafning eng uzun yo'liga teng bo'lishi mumkin. Zanjir ko'rinishidagi V vertexli grafda rekursiv DFS O(V) chuqurlikka tushadi.

Grid — implicit graf

Ko'p masalalarda graf to'g'ridan-to'g'ri adjacency list sifatida berilmaydi. 2D grid ham implicit graf: har katak vertex, qo'shni kataklar esa edge'lar. Odatda 4 yo'nalish ishlatiladi: yuqori, pastki, chap, o'ng.

Grid:
+---+---+---+
| 1 | 1 | 0 |
+---+---+---+
| 1 | 0 | 1 |
+---+---+---+
| 0 | 1 | 1 |
+---+---+---+

(0,0) ning qo'shnilari: (0,1) va (1,0)
(1,1) ning qo'shnilari: (0,1), (2,1), (1,0), (1,2)

4 yo'nalish vektori:

directions = [(0,1), (0,-1), (1,0), (-1,0)]
             // o'ng   chap   past   yuqori

FOR har bir (dr, dc) directions ichida
    new_row = row + dr
    new_col = col + dc
    IF 0 ≤ new_row < qatorlar_soni VA 0 ≤ new_col < ustunlar_soni
        // qo'shni katak — ko'rib chiqilishi mumkin

Gridda visited ni alohida to'plamda yoki grid qiymatini o'zgartirib boshqarish mumkin. Qiymatni o'zgartirish xotirani tejaydi, lekin asl gridni buzadi — ba'zan bu ruxsat etilmaydi yoki bir necha traversalda muammo keltirib chiqaradi.

8 yo'nalishli (diagonal ham kirgan) traversal uchun direction vektori 8 ta bo'ladi.

Grid traversalini BFS bilan

BFS gridda "eng kam qadam" masofasini topadi:

FUNCTION BFS_GRID(grid, start_row, start_col, target_row, target_col)
    queue   = [(start_row, start_col, 0)]   // (row, col, masofa)
    visited = {(start_row, start_col)}

    WHILE queue bo'sh emas
        (row, col, dist) = queue.DEQUEUE()

        IF row = target_row VA col = target_col
            RETURN dist

        FOR har bir (dr, dc) yo'nalishlar ichida
            nr = row + dr
            nc = col + dc

            IF chegarada VA (nr, nc) visited ichida bo'lmasa VA o'tish mumkin
                visited ga (nr, nc) ni qo'sh
                queue.ENQUEUE((nr, nc, dist + 1))

    RETURN -1   // yetib bo'lmaydi

Grid traversalini DFS bilan

DFS gridda barcha yo'llarni ko'rib chiqishda yoki connected componentlarni topishda qulay:

FUNCTION DFS_GRID(grid, row, col, visited)
    IF row chegaradan tashqarida
        RETURN
    IF col chegaradan tashqarida
        RETURN
    IF (row, col) visited ichida bo'lsa
        RETURN
    IF grid[row][col] qayta ishlanmaydigan qiymat
        RETURN

    visited ga (row, col) ni qo'sh
    PROCESS (row, col)

    DFS_GRID(grid, row+1, col, visited)
    DFS_GRID(grid, row-1, col, visited)
    DFS_GRID(grid, row, col+1, visited)
    DFS_GRID(grid, row, col-1, visited)

Disconnected grafni to'liq traversal qilish

Bitta startdan BFS yoki DFS faqat shu start bilan bog'liq componentni ko'radi. Barcha componentlarni qamrab olish uchun barcha vertexlardan yangi traversal boshlanadi:

FUNCTION TRAVERSE_ALL_COMPONENTS(graph)
    visited         = bo'sh set
    component_count = 0

    FOR har bir vertex graph ichida
        IF vertex visited ichida bo'lmasa
            component_count = component_count + 1
            DFS(graph, vertex, visited)   // yoki BFS

    RETURN component_count

Har yangi start — yangi component. Boshlanishlar soni undirected grafdagi connected componentlar soniga teng. Jami vaqt baribir O(V + E) — har vertex va edge bir marta ko'riladi.

BFS va DFS taqqoslanishi

Ikkala algoritm ham O(V + E) vaqt oladi. Farq nima kerakligida:

Xususiyat BFS DFS
Asosiy tuzilma Queue (FIFO) Stack yoki call stack
Yurish tartibi Qatlamma-qatlam Bir yo'l bo'ylab chuqurlab
Unweighted shortest path Kafolatlaydi Kafolatlamaydi
Cycle detection Mumkin Tabiiy va sodda
Topological sort Kahn algoritmi (in-degree) Postorder DFS
Xotira (worst case) Keng qatlamda O(V) Chuqur yo'lda O(V)
Vaqt (adjacency list) O(V + E) O(V + E)
Vaqt (adjacency matrix) O(V²) O(V²)

BFS tanlanadi:

  • Og'irliksiz grafda eng qisqa path kerak bo'lsa
  • Qatlamlar bo'yicha qayta ishlash kerak bo'lsa
  • Multi-source tarqalishi kerak bo'lsa (bir necha manbadan bir vaqtda)
  • Maqsad boshlang'ichga yaqin bo'lishi kutilsa

DFS tanlanadi:

  • Cycle detection kerak bo'lsa
  • Topological sort kerak bo'lsa
  • Barcha yo'llar ko'rib chiqilishi kerak bo'lsa (backtracking bilan)
  • Connected componentlar topish kerak bo'lsa
  • Labirint yoki path mavjudligi tekshirilsa

Note

BFS va DFS ikkalasi ham "grafda mavjudmi" savoliga javob beradi, ikkalasi ham connected componentlarni topadi. Farq shortest path kafolati va traversal tartibida — bu ikki omil tanlovni belgilaydi.

Keng tarqalgan xatolar

Visited ni dequeue/pop paytida qo'yish

BFSda bir vertex bir nechta yo'l orqali queuega bir necha marta tushishi mumkin. Dequeue paytida tekshirish ish bajarilishini to'g'ri qilib qo'ysa ham, takroriy enqueue queueni keraksiz kattalashtiradi. Enqueue paytida qo'yish optimal.

Directed grafda undirected cycle detection logikasini ishlatish

Undirected grafda "visited va ota bo'lmagan" qoidasi ishlaydi. Directed grafda hozirgi DFS yo'lidagi vertex kerak — in_stack to'plami. Ikkalasini aralashtirish false positive yoki false negative beradi.

Grid chegarasini tekshirmaslik

Qo'shni katak indeksi salbiy yoki grid o'lchamidan katta bo'lishi mumkin. Har yo'nalishda new_row va new_col chegarada ekanligini tekshirish shart — aks holda out-of-bounds xatosi.

Postorder DFS natijasini teskari qilishni unutish

Topological sort uchun postorder DFS natijasi teskari o'qilishi kerak. Natijani to'g'ridan-to'g'ri o'qish noto'g'ri tartib beradi.

Rekursiv DFS uchun juda chuqur graflar

Juda chuqur yoki zanjirsimon grafda rekursiya juda chuqur tushadi. Katta graflarda explicit stackli iterativ DFS xavfsizroq.

BFS weighted grafda shortest path beradi deb taxmin qilish

BFS eng kam qirralar sonini topadi. Og'irliklar har xil bo'lsa, qirralar soni minimal bo'lgan path og'irlik yig'indisi minimal bo'lmasligi mumkin. Manfiy bo'lmagan og'irliklarda Dijkstra kabi algoritm kerak.

Xulosa

BFS va DFS grafni to'liq ko'rib chiqishning ikki yo'li. Ikkalasi ham O(V + E) vaqt oladi, ikkalasi ham barcha reachable vertexlarni topadi. Farq traversal tartibida: BFS masofa qatlamlari bo'yicha, DFS bir yo'l bo'ylab chuqurlashib.

BFS unweighted grafda eng qisqa pathni kafolatlaydi va multi-source tarqalishi uchun tabiiy. DFS cycle detection, topological sort va backtrackingga tabiiy mos keladi.

Grafni ko'rib chiqishda visited nazorati muhim — cycle yoki parallel yo'llar sababli takroriy ko'rib chiqish oldini olish kerak. Undirected grafda bitta componentni ko'rish uchun bitta start, barcha componentlar uchun barcha vertexlardan yangi traversal kerak.

Grid traversalida graf adjacency list shaklida berilmaydi — qo'shnilar koordinatadan hisoblanadi. Bu implicit graf deb ataladi va xotirani tejaydi.

Dijkstra, topological sort, shortest path reconstruction va ko'plab klassik masalalar BFS va DFS ustiga qurilgan. Shuning uchun bu ikki algoritmni mustahkam o'zlashtirish qolgan graf algoritmlarini tushunish uchun poydevor hisoblanadi.