Frame del contenuto
Salta la navigazione con i breadcrumb
Home  freccia Capitolo 7. Grafi  freccia Panoramica, animazioni ed esercizi svolti

Panoramica, animazioni ed esercizi svolti

Panoramica del capitolo

In questo capitolo esaminiamo le caratteristiche principali dei grafi, fornendo le definizioni relative a tali strutture. Mostriamo come attraverso di essi sia possibile modellare una quantità di situazioni e come molti problemi possano essere interpretati come problemi su grafi, descrivendo alcuni algoritmi di base per operare su di essi.

Animazioni

L'animazione che state per guardare è in inglese e lo pseudo-codice in essa incluso è la naturale traduzione in inglese di quello presente nel libro. Pensiamo che ciò possa fornirvi uno spunto per contestualizzare gli argomenti studiati durante il corso nella lingua più frequentemente usata nel mondo del lavoro e della ricerca nell'ambito dell'informatica.

  1. Potete guardare l'animazione Visita in ampiezza di un grafo con n vertici a partire dal vertice s, utilizzando una coda Q inizialmente vuota e un array raggiunto per marcare i vertici visitati relativa al codice 7.1 di pagina 220.
  2. Potete guardare l'animazione Visita in profondità di un grafo utilizzando una pila P di archi, inizialmente vuota relativa al codice 7.4 di pagina 226.
  3. Potete guardare l'animazione Ordinamento topologico di un grafo orientato aciclico relativa al codice 7.7 di pagina 231.
  4. Potete guardare l'animazione Stampa delle componenti fortemente connesse in un grafo orientato relativa al codice 7.8 di pagina 237.
  5. Potete guardare l'animazione Algoritmo di Dijkstra per la ricerca dei cammini minimi single source, dove la variabile elemento indica un nuovo elemento allocato relativa al codice 7.9 di pagina 245.
  6. Potete guardare l'animazione Algoritmo di Bellman-Ford per la ricerca dei cammini minimi single source relativa al codice 7.10 di pagina 251.
  7. Potete guardare l'animazione Algoritmo di Floyd-Warshall per la ricerca dei cammini minimi all pairs relativa al codice 7.11 di pagina 255.
  8. Potete guardare l'animazione Algoritmo di Kruskal per la ricerca del minimo albero di ricoprimento relativa al codice 7.12 di pagina 262.
  9. Potete guardare l'animazione Algoritmo di Jarník-Prim per la ricerca del minimo albero di ricoprimento relativa al codice 7.13 di pagina 267.

Esercizi svolti

  1. Fate clic qui per il download del file PDF con lo svolgimento degli esercizi 7.1, 7.3, 7.4.





Pearson Italia S.p.A. © 2013, tutti i diritti riservati, P.I. 07415430011.
Privacy policy

Torna in cima alla pagina