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

IndexError: list index out of range la un graf cu noduri numerotate de la 1

Pe scurt

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

Greșit
PYTHON
graf = [[] for _ in range(n)]
for a, b in muchii:
    graf[a].append(b)
    graf[b].append(a)
Corect
PYTHON
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

Greșit
PYTHON
dist = [float('inf')] * n
dist[start] = 0
Corect
PYTHON
dist = [float('inf')] * (n + 1)
dist[start] = 0

Toate listele indexate după nod trebuie să aibă aceeași dimensiune, n + 1. Când afișezi rezultatul, sari poziția 0: dist[1:].

Repară tu

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

Codul care dă eroarea
PYTHON
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, []))
După reparație, programul afișează
[2, 2, 1, 1]
[0]
Indiciu

Ai nevoie de o listă pentru fiecare număr de la 1 la n, inclusiv n.

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

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