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

KeyError: 'D' la graf[nod] (nodul nu are listă de vecini)

Pe scurt

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

Greșit
PYTHON
graf = {'A': ['B', 'C'], 'B': ['D']}
for v in graf['D']:
    print(v)
Corect
PYTHON
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

Greșit
PYTHON
graf = {}
for a, b in muchii:
    graf.setdefault(a, []).append(b)
Corect
PYTHON
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ă tu

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.

Codul care dă eroarea
PYTHON
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'))
După reparație, programul afișează
True
False
True
Indiciu

Un nod care nu e cheie în dicționar nu are vecini.

Alte forme ale mesajului

  • KeyError: 4
  • KeyError: '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

← 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.