Graful neorientat are muchiile adăugate doar într-un sens: BFS nu ajunge la toate nodurile
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ă
for u, v in muchii:
graf[u].append(v)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
for curs, cerinta in dependente:
graf[curs].append(cerinta)
graf[cerinta].append(curs)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ă 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.
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)4 4 1
Indiciu
Fiecare tunel trebuie adăugat în lista ambelor stații.
Reparația
from collections import defaultdict, deque
def statii_accesibile(muchii, start):
graf = defaultdict(list)
for u, v in muchii:
graf[u].append(v)
graf[v].append(u)
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)De ce merge
Cu muchiile doar în sensul u → v, din C se putea merge doar spre D, deci BFS-ul găsea 2 stații în loc de 4. Adăugând și graf[v].append(u), fiecare tunel poate fi parcurs în ambele sensuri. Din A rezultatul era corect și înainte, de aceea greșeala se vede doar când pornești din mijlocul sau din capătul celălalt al liniei.
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
KeyError: 'D' la graf[nod] (nodul nu are listă de vecini) Graful e un dicționar de liste de vecini, dar un nod apare doar ca vecin, nu și ca cheie (de obicei un nod fără muchii de ieșire). graf[nod] dă KeyError. Folosește graf.get(nod, []) sau construiește graful cu defaultdict(list) și adaugă toate nodurile. TypeError: first argument must be callable or None defaultdict primește o funcție care creează valoarea implicită, nu valoarea însăși. Scrie defaultdict(int) pentru 0, defaultdict(list) pentru [], defaultdict(set) pentru set(), nu defaultdict(0) sau defaultdict([]). BFS cu coada.pop() în loc de popleft(): distanțele ies prea mari pop() scoate ultimul element, deci coada ta funcționează ca o stivă și parcurgerea devine DFS. Nodurile sunt descoperite pe drumuri lungi și primesc distanțe prea mari. La BFS folosește deque și scoate cu popleft() (cel mai vechi element). Î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.
