...
Eroare Algoritmi și structuri de date · Grafuri: BFS și DFS

Graful neorientat are muchiile adăugate doar într-un sens: BFS nu ajunge la toate nodurile

Pe scurt

Pentru un graf neorientat (drumuri, prietenii, cabluri), fiecare muchie u-v trebuie adăugată în ambele liste: graf[u].append(v) și graf[v].append(u). Cu un singur sens, din v nu mai poți ajunge înapoi la u, iar BFS/DFS ratează noduri.

Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la

Ce înseamnă

Lista de muchii [(u, v), ...] nu spune singură dacă graful e orientat. Dacă problema descrie legături în ambele sensuri (o stradă cu dublu sens, o prietenie, un cablu de rețea), graful e neorientat, iar lista de adiacență trebuie să conțină muchia de la u la v și de la v la u.

Când adaugi doar graf[u].append(v), parcurgerea pornită din u merge, dar cea pornită din alt nod poate rămâne blocată: din C nu există drum înapoi spre A și B. Rezultatul: componente conexe prea multe, distanțe infinite, „nu se poate ajunge” deși se poate. Dacă folosești dict simplu în loc de defaultdict, poți primi și KeyError pentru nodurile care apar doar ca destinație.

Citește atent enunțul: „orientat”, „cu sens unic”, „A depinde de B” înseamnă un singur sens; „legat”, „vecin”, „drum între” de obicei înseamnă ambele.

De ce apare: cauzele frecvente

1Muchia adăugată o singură dată

Greșit
PYTHON
for u, v in muchii:
    graf[u].append(v)
Corect
PYTHON
for u, v in muchii:
    graf[u].append(v)
    graf[v].append(u)

Într-un graf neorientat legătura merge în ambele sensuri, deci apare în ambele liste.

2Graf orientat tratat ca neorientat

Greșit
PYTHON
for curs, cerinta in dependente:
    graf[curs].append(cerinta)
    graf[cerinta].append(curs)
Corect
PYTHON
for curs, cerinta in dependente:
    graf[cerinta].append(curs)

Dependențele au sens. Dacă le pui în ambele sensuri, sortarea topologică vede cicluri peste tot.

Repară tu

Repară eroarea, direct în pagină

Funcția statii_accesibile(muchii, start) numără câte stații de metrou pot fi atinse din start; tunelurile merg în ambele sensuri. Testul cu assert pică pentru stația C. Repar-o ca testele să treacă și să afișeze 4, 4 și 1.

Codul care dă eroarea
PYTHON
from collections import defaultdict, deque

def statii_accesibile(muchii, start):
    graf = defaultdict(list)
    for u, v in muchii:
        graf[u].append(v)
    vazute = {start}
    coada = deque([start])
    while coada:
        u = coada.popleft()
        for v in graf[u]:
            if v not in vazute:
                vazute.add(v)
                coada.append(v)
    return len(vazute)

muchii = [('A', 'B'), ('B', 'C'), ('C', 'D')]
for start, corect in [('A', 4), ('C', 4), ('X', 1)]:
    rez = statii_accesibile(muchii, start)
    assert rez == corect, f'statii gresite din {start}: {rez}'
    print(rez)
După reparație, programul afișează
4
4
1
Indiciu

Fiecare tunel trebuie adăugat în lista ambelor stații.

Cum o eviți pe viitor

Când construiești graful, scrie lângă cod un comentariu: „neorientat” sau „orientat de la X la Y”. Folosește defaultdict(list) și pune ambele sensuri imediat pentru grafurile neorientate. Testează parcurgerea pornind și din ultimul nod, nu doar din primul: o greșeală de sens apare imediat.

Întrebări frecvente

Muchiile duble nu dublează timpul BFS?

Fiecare muchie apare de două ori, deci BFS e O(V + 2E), adică tot O(V + E). Nu contează în complexitate.

Cum îmi dau seama din date că e neorientat?

De obicei din enunț. Dacă apare atât (u, v), cât și (v, u) în listă, graful e probabil orientat și muchiile sunt deja în ambele sensuri.

Erori înrudite

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție

Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.