Graflar: DFS va BFS

Graf

Graf — uchlar va ularni bog‘lovchi qirralar (shaharlar va yo‘llar, labirint kataklari).

g = [[] for _ in range(n + 1)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u].append(v); g[v].append(u)

Asosiy algoritmlar

BFS (collections.deque): og‘irliksiz grafda eng qisqa yo‘l, labirint.
DFS: bog‘langanlik, komponentlar.
Dijkstra (heapq): musbat og‘irlikli eng qisqa yo‘l, O(m log n).
Kruskal + DSU: minimal skelet daraxt.

Chuqur rekursiyada Python to‘xtaydi — DFS ni stek bilan yozing yoki BFS ishlating.

BFS

BFS (kenglik bo‘yicha qidiruv) — boshlang‘ich uchdan qatlam-qatlam yuradi: avval masofasi 1 bo‘lganlar, keyin 2… Shuning uchun qirralar vazni bir xil bo‘lsa, eng qisqa yo‘lni beradi. O(V + E).

from collections import deque

dist = [-1] * n
dist[s] = 0
q = deque([s])
while q:
    v = q.popleft()
    for to in g[v]:
        if dist[to] == -1:
            dist[to] = dist[v] + 1
            q.append(to)

To‘rda (labirint)

for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
    nr, nc = r + dr, c + dc
    if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] != "#" and dist[nr][nc] == -1:
        ...

Diqqat

Uchni navbatga qo‘shganda belgilang, olganda emas — aks holda bir uch ko‘p marta kiradi.
Bir nechta boshlang‘ich nuqta bo‘lsa (masalan, bir nechta olov manbai), hammasini birdan navbatga qo‘ying.

DFS

DFS (chuqurlik bo‘yicha qidiruv) — bir yo‘ldan oxirigacha boradi, keyin orqaga qaytadi. O(V + E).

import sys
sys.setrecursionlimit(10**6)

seen = [False] * n
def dfs(v):
    seen[v] = True
    for to in g[v]:
        if not seen[to]:
            dfs(to)

components = 0
for v in range(n):
    if not seen[v]:
        components += 1
        dfs(v)

Nimalarni topadi

Bog‘lanish komponentalari soni (yuqoridagi kod).
Sikl borligi: yo‘naltirilgan grafda «hozir stekda turgan» uchga qaytish — sikl.
Topologik tartib: DFS tugagan tartibni teskari aylantiring.
To‘rdagi «orollar» soni.

Katta grafda rekursiya chuqurligi muammo bo‘lsa, DFS ni oddiy stek bilan yozing.

Topologik saralash

Yo‘naltirilgan, sikli yo‘q grafda uchlarni shunday tartiblaymizki, har bir u → v qirrada u oldin keladi. Masalan, fanlar ketma-ketligi yoki bir-biriga bog‘liq vazifalar.

Kan algoritmi: kiruvchi qirrasi yo‘q uchlardan boshlab, ularni navbat bilan olib tashlaymiz.

from collections import deque

indeg = [0] * (n + 1)
for u in range(1, n + 1):
    for v in g[u]:
        indeg[v] += 1
q = deque(u for u in range(1, n + 1) if indeg[u] == 0)
order = []
while q:
    u = q.popleft()
    order.append(u)
    for v in g[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)

len(order) < n bo‘lsa, grafda sikl bor va bunday tartib mavjud emas.

Nazariya