Grafi: nodi e archi

Non tutto è una lista. Un grafo è puntini e frecce: rete, dipendenze, mappe.

Il disegno

Stessi puntini, domande diverse.

Visitare

Ordine in cui tocchi i nodi.

Come lo tieni

Memoria vs velocità sul “chi è vicino”.

pezzo selezionato

BFS

Coda. Livello per livello. Cammino minimo se gli archi valgono 1.

Da ricordare

Usa una coda, non la ricorsione. Lo stack esplode sui grafi larghi.

In poche righe

Diretto o no, pesato o no. Lista di adiacenza vs matrice: n piccolo e denso → matrice; sparso → liste. BFS: onde da un nodo (code). DFS: tuffo (pila).

Cammino minimo (Dijkstra) se i pesi sono ≥ 0. Topological sort se è un DAG: l’ordine di build, di course, di make.

Disegna questo

Cinque nodi, alcune frecce. Un BFS cerchiato a onde. Un ciclo evidenziato: lì il topo-sort esplode.

Un foglio, non un software. Se lo sai ridisegnare senza guardare, la lezione è tua.

Giusto, poi veloce Quiz di questo corso