Grafuri: noduri, muchii, liste de adiacență
Orașele legate prin autostrăzi, prietenii dintr-o rețea socială, stațiile de metrou, paginile web cu linkuri între ele: toate sunt grafuri. Arborii pe care i-ai studiat sunt un caz particular. În această lecție înveți vocabularul și cum reții un graf în Python, ca să poți rula pe el algoritmii din lecțiile următoare.
Vocabularul grafurilor
Un arbore este un graf conex fără cicluri, cu o rădăcină. Un graf general poate avea cicluri, noduri izolate și mai multe drumuri între aceleași două noduri. De aceea algoritmii pe grafuri țin minte nodurile vizitate.
Scrie construieste_graf(muchii), care returnează un graf neorientat ca defaultdict(list), și grade(graf), care returnează un dicționar nod → grad (numărul de vecini), în ordinea cheilor din graf. Testele afișează vecinii fiecărui oraș, sort…
- construieste_graf: pentru fiecare (a, b) adaugă b la vecinii lui a și a la vecinii lui b.
- grade: pentru fiecare nod, len(graf[nod]).
- Prima linie trebuie să fie Brașov -> ['București', 'Cluj'], iar ultima {} (graful fără muchii).
Restul explicațiilor, editorul și verificarea automată se deblochează cu Arbori, grafuri și heap.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan