...
Algoritmi pe grafuri

BFS și DFS: parcurgerea în lățime și în adâncime a unui graf

Pe scurt

BFS (parcurgerea în lățime) și DFS (parcurgerea în adâncime) sunt cele două moduri de bază de a vizita toate nodurile unui graf. BFS pornește dintr-un nod și vizitează întâi toți vecinii lui, apoi vecinii vecinilor, folosind o coadă. DFS merge cât de departe poate pe un drum, apoi se întoarce, folosind o stivă sau recursivitatea. Pe ele se construiesc drumul minim, componentele conexe și detectarea ciclurilor.

  • O(n + m)pentru n noduri și m muchii
  • coadăîn BFS
  • stivăîn DFS (sau recursivitate)
  • 2lecții gratuite, fără card
BFS · PARCURGERE ÎN LĂȚIME ABCDEF O(n + m) BFS · DFS

BFS și DFS, în animație

Alege parcurgerea și apasă „Pornește”. Nodul galben e cel curent, cele verzi sunt vizitate, iar sub graf vezi coada (BFS) sau stiva de apeluri (DFS).

Cum funcționează BFS și DFS

BFS: pui nodul de start într-o coadă și îl marchezi. Cât timp coada nu e goală, scoți primul nod, îl vizitezi și pui în coadă toți vecinii lui nemarcați. Nodurile ies în ordinea distanței față de start: întâi cele la o muchie, apoi cele la două și așa mai departe. De aceea BFS găsește drumul cu cele mai puține muchii.

DFS: vizitezi nodul, apoi apelezi DFS pe primul vecin nevizitat, care face la fel, până ajungi într-un nod fără vecini noi. Atunci te întorci (exact ca la backtracking) și încerci următorul vecin. Implementarea recursivă folosește stiva de apeluri; cea iterativă, o stivă explicită.

BFS și DFS în C++, Python și Java

Graful e ținut ca listă de adiacență: pentru fiecare nod, lista vecinilor. Este reprezentarea folosită aproape mereu.

from collections import deque

graf = {
    "A": ["B", "C"], "B": ["A", "D", "E"], "C": ["A", "E"],
    "D": ["B", "F"], "E": ["B", "C", "F"], "F": ["D", "E"],
}


def bfs(start):
    vizitat, coada, ordine = {start}, deque([start]), []
    while coada:
        nod = coada.popleft()
        ordine.append(nod)
        for vecin in graf[nod]:
            if vecin not in vizitat:
                vizitat.add(vecin)
                coada.append(vecin)
    return ordine


def dfs(nod, vizitat=None):
    vizitat = vizitat if vizitat is not None else []
    vizitat.append(nod)
    for vecin in graf[nod]:
        if vecin not in vizitat:
            dfs(vecin, vizitat)
    return vizitat


print(bfs("A"))   # ['A', 'B', 'C', 'D', 'E', 'F']
print(dfs("A"))   # ['A', 'B', 'D', 'F', 'E', 'C']

Încearcă: numărul de insule de pe o hartă

Problema clasică de interviu pentru DFS, din lecția 116 a cursului de algoritmi. Verificarea e pe loc.

Exercițiu din lecția 116 · cursul de algoritmi

Numărul de insule dintr-o hartă

Scrie numar_insule(harta) și aria_maxima(harta) pentru o hartă dată ca listă de texte ('1' = uscat, '0' = apă), cu 4 vecini (sus, jos, stânga, dreapta). Nu modifica harta primită: lucrează pe o copie de tip listă de liste.

  1. Copiază harta: grila = [list(rand) for rand in harta].
  2. Pentru fiecare celulă '1': crești contorul și pornești un DFS care transformă insula în '0'.
  3. Pentru arie, DFS-ul întoarce 1 + suma ariilor vecinilor, iar tu păstrezi maximul.
  4. Trebuie să apară: 1, 3, 0, 1, 9, 4, 0 și la final 11000 (harta originală neschimbată).
Indiciu: Verifică marginile înainte să citești grila[r][c]: r < 0 or r >= randuri or c < 0 or c >= coloane.
def numar_insule(harta):
    grila = [list(rand) for rand in harta]
    randuri = len(grila)
    coloane = len(grila[0]) if grila else 0

    def scufunda(r, c):
        if r < 0 or r >= randuri or c < 0 or c >= coloane or grila[r][c] != '1':
            return
        grila[r][c] = '0'
        scufunda(r - 1, c)
        scufunda(r + 1, c)
        scufunda(r, c - 1)
        scufunda(r, c + 1)

    insule = 0
    for r in range(randuri):
        for c in range(coloane):
            if grila[r][c] == '1':
                insule += 1
                scufunda(r, c)
    return insule


def aria_maxima(harta):
    grila = [list(rand) for rand in harta]
    randuri = len(grila)
    coloane = len(grila[0]) if grila else 0

    def arie(r, c):
        if r < 0 or r >= randuri or c < 0 or c >= coloane or grila[r][c] != '1':
            return 0
        grila[r][c] = '0'
        return 1 + arie(r - 1, c) + arie(r + 1, c) + arie(r, c - 1) + arie(r, c + 1)

    maxim = 0
    for r in range(randuri):
        for c in range(coloane):
            if grila[r][c] == '1':
                maxim = max(maxim, arie(r, c))
    return maxim


harta1 = ['11110',
          '11010',
          '11000',
          '00000']
harta2 = ['11000',
          '11000',
          '00100',
          '00011']
harta3 = ['000',
          '000']

print(numar_insule(harta1))
print(numar_insule(harta2))
print(numar_insule(harta3))
print(numar_insule(['1']))
print(aria_maxima(harta1))
print(aria_maxima(harta2))
print(aria_maxima(harta3))
print(harta2[0])
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

BFS sau DFS?

BFSDFS
Structura folosităcoadăstivă / recursivitate
Ordineanivel cu nivelmerge în adâncime, apoi revine
Drum minim (fără costuri)danu
Componente conexedada, cel mai des
Detectarea ciclurilor, sortare topologicăse poateda, natural
Memoriecât cel mai lat nivelcât cel mai lung drum
ComplexitateO(n + m)O(n + m)

Dacă muchiile au costuri diferite, BFS nu mai dă drumul cel mai ieftin; atunci folosești algoritmul lui Dijkstra.

Grafuri la BAC și la interviuri

La BAC Informatică, profilul mate-info, apar grafuri neorientate și orientate: grade, lanțuri, cicluri, componente conexe, iar parcurgerile BFS și DFS se cer ca ordine de vizitare pornind dintr-un nod dat. La interviuri, problemele tipice sunt numărul de insule (componente conexe pe o grilă), drumul minim într-un labirint, detectarea unui ciclu și ordinea cursurilor (sortare topologică).

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

M-am inscris la cursurile de programare online gratuite, dupa care am achizitionat cursurile de java incepatori si intermediari. Foarte bune

Fotografia lui Madalina Pitrop, cursant al Academiei ProgramatorilorMadalina PitropRecenzie pe Google

Foarte profi si utile cursurile. Practica aplicata si explicata de traineri inarmati cu rabdare si cunostine solide.

Fotografia lui Iulian Pahom, cursant al Academiei ProgramatorilorIulian PahomRecenzie pe Google

Cursuri foarte utile si profesori foarte pregatiti. Recomand cu toata increderea.

Fotografia lui Catalina Ioana Dan, cursant al Academiei ProgramatorilorCatalina Ioana DanRecenzie pe Google

Întrebări frecvente

Ce este BFS?

BFS (Breadth-First Search, parcurgerea în lățime) este un algoritm care vizitează nodurile unui graf nivel cu nivel: întâi nodul de start, apoi toți vecinii lui, apoi vecinii acestora. Folosește o coadă și găsește drumul cu cel mai mic număr de muchii.

Ce este DFS?

DFS (Depth-First Search, parcurgerea în adâncime) este un algoritm care pornește dintr-un nod și merge cât de departe poate pe un drum, apoi se întoarce și încearcă alte ramuri. Se implementează recursiv sau cu o stivă.

Care e diferența dintre BFS și DFS?

BFS folosește o coadă și vizitează nodurile în ordinea distanței față de start, deci găsește drumul minim într-un graf fără costuri. DFS folosește o stivă și merge în adâncime, fiind potrivit pentru componente conexe, cicluri și sortare topologică. Ambele au complexitatea O(n + m).

Ce complexitate au BFS și DFS?

O(n + m), unde n este numărul de noduri și m numărul de muchii, dacă graful e reținut ca listă de adiacență. Cu matrice de adiacență, complexitatea devine O(n²).

Cum găsesc drumul minim cu BFS?

Ții pentru fiecare nod distanța și nodul din care ai ajuns în el. Când pui un vecin nou în coadă, distanța lui este distanța nodului curent plus 1. La final, refaci drumul mergând înapoi pe nodurile părinte. Funcționează doar dacă toate muchiile au același cost.

Unde exersez BFS și DFS?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor ai lecții despre liste de adiacență, BFS, DFS, cicluri, Dijkstra și grafuri bipartite, cu probleme rezolvate în Python direct în browser. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.