Grafi, cenni preliminari: grafi diretti, non diretti, vicinato e grado di un nodo, cammini, cicli. Operatori basilari su grafi: creazione di un grafo; verifica dell'esistenza di un arco; inserimento di un nuovo arco; cancellazione di un arco; inserimento di un nuovo nodo; cancellazione di un nodo. Rappresentazioni dei grafi (e degli operatori) col calcolatore: Liste di archi; Matrice di adiacenza; Vettore di liste di adiacenza (con implementazione dettagliata in C, vedere slides). Valutazione delle tre rappresentazioni dal punto di vista della complessita' computazionale.
Per un esempio di utilizzo delle primitive su grafi definite a lezione si veda il programma simple.c nella cartella examples della libreria per la gestione dei grafi libgraphs.zip. Per le istruzioni di compilazione si faccia riferimento al file readme.txt che si trova all'interno dell'archivio.
Iscriviti a:
Commenti sul post (Atom)
Post
Nessun commento:
Posta un commento