BFS: cel mai scurt drum într-un graf
Câte schimbări de tren îți trebuie ca să ajungi dintr-o stație în alta? Câți „prieteni ai prietenilor” te despart de cineva pe o rețea socială? Când toate muchiile „costă” la fel, parcurgerea în lățime (BFS) găsește cel mai scurt drum. Ai folosit-o deja pe arbori, nivel cu nivel; pe grafuri adaugi doar evidența nodurilor vizitate.
Ideea: unde de apă
BFS pornește din nodul de start și explorează în cercuri: întâi toți vecinii (distanța 1), apoi vecinii lor nevizitați (distanța 2) și așa mai departe, ca undele unei pietre aruncate în apă.
Scrie distante(graf, start), care returnează dicționarul distanțelor (în număr de muchii) de la start la fiecare nod accesibil, în ordinea descoperirii, și drum(graf, a, b), care returnează cel mai scurt drum ca listă de noduri (sau [] dacă…
- distante: deque([start]), popleft, iar fiecare vecin nou primește distanta[nod] + 1.
- drum: ține un dicționar parinte, apoi urcă din b până la None și inversează.
- Trebuie să apară {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}, ..., [0, 1, 3, 5], [4, 2, 0, 1], [2], [].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan