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.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
La multe probleme de grafuri (rețele de servere, orașe, persoane) nodurile sunt date ca numere de la 1 la n, iar muchiile ca perechi (a, b). Dacă reprezinți graful ca listă de liste cu n elemente, indicii valizi sunt 0..n-1. Muchia care atinge nodul n cere graf[n], o poziție care nu există, și primești list index out of range.
Aceeași problemă apare la listele auxiliare: dist = [inf] * n, vizitat = [False] * n, grad = [0] * n. Toate trebuie să aibă n + 1 poziții când nodurile încep de la 1.
Nu încerca să scazi 1 peste tot (graf[a - 1]): e ușor să uiți într-un loc și să amesteci convențiile. Varianta mai sigură este o poziție în plus, iar poziția 0 rămâne nefolosită.
De ce apare: cauzele frecvente
1Lista de adiacență are doar n poziții
graf = [[] for _ in range(n)]
for a, b in muchii:
graf[a].append(b)
graf[b].append(a)graf = [[] for _ in range(n + 1)]
for a, b in muchii:
graf[a].append(b)
graf[b].append(a)Cu n + 1 liste, indicii 1..n sunt toți valizi. Poziția 0 rămâne goală și nu încurcă.
2Listele auxiliare au altă dimensiune decât graful
dist = [float('inf')] * n
dist[start] = 0dist = [float('inf')] * (n + 1)
dist[start] = 0Toate listele indexate după nod trebuie să aibă aceeași dimensiune, n + 1. Când afișezi rezultatul, sari poziția 0: dist[1:].
Repară eroarea, direct în pagină
Funcția vecini_pe_nod(n, muchii) construiește lista de adiacență a unei rețele cu servere numerotate de la 1 la n și returnează câți vecini are fiecare server, de la 1 la n. Codul dă IndexError: list index out of range. Repar-o ca să afișeze [2, 2, 1, 1] și [0].
def vecini_pe_nod(n, muchii):
graf = [[] for _ in range(n)]
for a, b in muchii:
graf[a].append(b)
graf[b].append(a)
return [len(graf[i]) for i in range(1, n + 1)]
print(vecini_pe_nod(4, [(1, 2), (1, 3), (2, 4)]))
print(vecini_pe_nod(1, []))[2, 2, 1, 1] [0]
Indiciu
Ai nevoie de o listă pentru fiecare număr de la 1 la n, inclusiv n.
Reparația
def vecini_pe_nod(n, muchii):
graf = [[] for _ in range(n + 1)]
for a, b in muchii:
graf[a].append(b)
graf[b].append(a)
return [len(graf[i]) for i in range(1, n + 1)]
print(vecini_pe_nod(4, [(1, 2), (1, 3), (2, 4)]))
print(vecini_pe_nod(1, []))De ce merge
Cu range(n), lista avea pozițiile 0..3, iar muchia (2, 4) cerea graf[4]. Pe al doilea test nici nu se ajungea la muchii: graf[1] nu exista într-o listă cu un singur element. Cu n + 1 liste, fiecare server de la 1 la n are poziția lui, iar poziția 0 rămâne nefolosită. Rezultatul se citește de la 1 la n: serverele 1 și 2 au câte doi vecini, 3 și 4 câte unul.
Alte forme ale mesajului
IndexError: list index out of range
Cum o eviți pe viitor
Citește atent enunțul: nodurile sunt de la 0 la n-1 sau de la 1 la n? Scrie convenția într-un comentariu și creează toate listele indexate după nod (graf, dist, vizitat, parinte) cu aceeași dimensiune. Dacă nodurile sunt texte sau numere rare (de exemplu 1, 50, 1000), folosește un dicționar în loc de listă.
Întrebări frecvente
Nu e risipă să las poziția 0 goală?
Este un singur element în plus, iar codul devine mult mai clar: nodul 5 e la poziția 5. La interviuri e o alegere obișnuită și ușor de explicat.
Când folosesc dicționar în loc de listă?
Când nodurile nu sunt numere consecutive (texte, coduri, numere rare). Un dicționar acceptă orice cheie imuabilă, dar trebuie să ai grijă la nodurile fără muchii (KeyError).
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. IndexError: list index out of range la dp[n] (tabelul DP e prea scurt) Ai creat tabelul cu dp = [0] * n, dar răspunsul e dp[n], iar o listă cu n elemente are doar indicii 0..n-1. Când dp[i] înseamnă „primele i elemente” sau „treapta i”, tabelul are nevoie de n + 1 poziții: dp = [0] * (n + 1). IndexError: list index out of range la lista[i + 1] Compari fiecare element cu următorul (lista[i] și lista[i + 1]), dar bucla merge până la ultimul element, care nu are un următor. Oprește bucla cu un pas mai devreme: for i in range(len(lista) - 1). Î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.
