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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Cel mai des reprezinți un graf ca dicționar: graf = {'A': ['B', 'C'], 'B': ['D']}. BFS și DFS citesc graf[nod] pentru fiecare nod descoperit. Dacă un nod apare în lista de vecini a altuia, dar nu are propria cheie (aici 'C' și 'D'), citirea graf['D'] dă KeyError: 'D'.
Situația e foarte frecventă la grafurile orientate: nodurile „finale” (fără muchii care pleacă din ele) nu sunt scrise ca chei. La fel când construiești graful dintr-o listă de muchii și adaugi doar graf[a].append(b), fără să creezi și cheia b, sau când nodul de start nu există în graf.
Valoarea afișată după KeyError este nodul lipsă. Reparațiile: graf.get(nod, []) la citire, sau un graf construit complet, cu fiecare nod cheie, eventual cu listă goală.
De ce apare: cauzele frecvente
1Noduri fără vecini lipsesc din dicționar
graf = {'A': ['B', 'C'], 'B': ['D']}
for v in graf['D']:
print(v)graf = {'A': ['B', 'C'], 'B': ['D']}
for v in graf.get('D', []):
print(v)get întoarce o listă goală pentru nodurile fără cheie, deci bucla pur și simplu nu rulează.
2Graful construit din muchii doar într-un sens
graf = {}
for a, b in muchii:
graf.setdefault(a, []).append(b)from collections import defaultdict
graf = defaultdict(list)
for a, b in muchii:
graf[a].append(b)
graf[b].append(a)Pentru un graf neorientat fiecare muchie se adaugă în ambele sensuri, deci ambele capete devin chei. La un graf orientat adaugă măcar graf[b] ca listă goală.
Repară eroarea, direct în pagină
Funcția poate_ajunge(graf, start, tinta) verifică cu DFS dacă există drum de la start la tinta într-un graf orientat de dependențe. Nodurile fără dependențe nu au cheie în dicționar, iar codul dă KeyError: 'D'. Repar-o ca să afișeze True, False și True.
def poate_ajunge(graf, start, tinta):
vazut = {start}
stiva = [start]
while stiva:
nod = stiva.pop()
if nod == tinta:
return True
for v in graf[nod]:
if v not in vazut:
vazut.add(v)
stiva.append(v)
return False
graf = {'A': ['B', 'C'], 'B': ['D'], 'C': []}
print(poate_ajunge(graf, 'A', 'C'))
print(poate_ajunge(graf, 'A', 'E'))
print(poate_ajunge(graf, 'D', 'D'))True False True
Indiciu
Un nod care nu e cheie în dicționar nu are vecini.
Reparația
def poate_ajunge(graf, start, tinta):
vazut = {start}
stiva = [start]
while stiva:
nod = stiva.pop()
if nod == tinta:
return True
for v in graf.get(nod, []):
if v not in vazut:
vazut.add(v)
stiva.append(v)
return False
graf = {'A': ['B', 'C'], 'B': ['D'], 'C': []}
print(poate_ajunge(graf, 'A', 'C'))
print(poate_ajunge(graf, 'A', 'E'))
print(poate_ajunge(graf, 'D', 'D'))De ce merge
Nodul 'D' apare ca vecin al lui 'B', dar nu are cheie proprie, pentru că nu depinde de nimic. Când DFS-ul ajungea la el, graf['D'] arunca KeyError. graf.get(nod, []) întoarce o listă goală pentru nodurile fără cheie, deci DFS-ul le vizitează fără să încerce să meargă mai departe. Pe al doilea test, DFS-ul vizitează A, C, B, D, nu găsește E și returnează False.
Alte forme ale mesajului
KeyError: 4KeyError: 'Bucuresti'
Cum o eviți pe viitor
Construiește graful într-o funcție separată, care garantează că fiecare nod e cheie: pornește de la lista tuturor nodurilor (graf = {n: [] for n in noduri}), apoi adaugă muchiile. Atenție cu defaultdict: citirea unei chei noi o creează, iar dacă faci asta în timp ce parcurgi graful primești RuntimeError: dictionary changed size during iteration. Testează pe un graf cu un nod fără muchii.
Întrebări frecvente
defaultdict rezolvă problema complet?
Rezolvă KeyError, pentru că o cheie lipsă devine o listă goală. Dar adaugă cheia în dicționar la prima citire, ceea ce poate da RuntimeError dacă în acel moment parcurgi chiar dicționarul.
De ce eroarea apare la un nod pe care nu l-am pus eu în cod?
Nodul a fost descoperit ca vecin al altui nod. BFS/DFS ajunge la el și încearcă să-i citească vecinii, care n-au fost definiți.
Erori înrudite
RuntimeError: dictionary changed size during iteration Parcurgi un dicționar (de obicei graful) cu for, iar în buclă adaugi sau ștergi chei. Cu defaultdict, chiar și citirea graf[v] pentru un nod nou adaugă o cheie. Parcurge list(graf) sau citește cu graf.get(v, []). KeyError: 'a' la frecv[litera] += 1 frecv[litera] += 1 citește întâi valoarea cheii, iar la prima apariție a literei cheia nu există încă. Folosește frecv[litera] = frecv.get(litera, 0) + 1, un defaultdict(int) sau direct Counter(text). IndexError: list index out of range la un graf cu noduri numerotate de la 1 Nodurile sunt numerotate de la 1 la n, dar lista de adiacență are n poziții (0..n-1), așa că graf[n] nu există. Creează n + 1 liste: graf = [[] for _ in range(n + 1)], și ignoră poziția 0. Î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.
