10. Graflar: BFS va DFS

Graf nima

Graf — tugunlar (vertex) va ularni bog‘lovchi qirralar (edge).
Shahar va yo‘llar, do‘stlar tarmog‘i, labirint kataklari — bularning
hammasi graf.

Tasvirlash

Qo‘shnilar ro‘yxati — eng ko‘p ishlatiladigan usul:

graf = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    graf[u].append(v)
    graf[v].append(u)      # yo‘naltirilmagan graf uchun

DFS — chuqurlikka

Bir yo‘nalishda oxirigacha borib, keyin qaytadi:

korilgan = [False] * (n + 1)

def dfs(u):
    korilgan[u] = True
    for v in graf[u]:
        if not korilgan[v]:
            dfs(v)

Nima uchun: bog‘langan qismlarni sanash, sikl topish, daraxtni
aylanish.

BFS — kenglikka

Qavat-qavat tarqaladi va eng qisqa yo‘lni (qirralar soni bo‘yicha)
topadi:

from collections import deque

masofa = [-1] * (n + 1)
masofa[boshlanish] = 0
navbat = deque([boshlanish])
while navbat:
    u = navbat.popleft()
    for v in graf[u]:
        if masofa[v] == -1:
            masofa[v] = masofa[u] + 1
            navbat.append(v)

deque shart: oddiy ro‘yxatda pop(0) O(n) vaqt oladi va butun
algoritm sekinlashadi.

Qaysi biri qachon

Murakkablik

Ikkalasi ham O(n + m): har bir tugun bir marta ko‘riladi, har bir
qirra bir marta tekshiriladi.

Rekursiv DFS xavfi

Zanjir shaklidagi grafda chuqurlik n ga yetadi. n = 10⁵ bo‘lsa,
rekursiya cheklovga uriladi — u holda DFS ni ham navbat (stek) bilan,
sikl ko‘rinishida yozish kerak.