Résumé de section

  • Lezione 26:  27/11/25
     
    • Definizione di grafo; terminologia; esempi applicativi
    • Concetti fondamentali: cammino, ciclo, grafo connesso, subgraph, spanning subgraph, albero (rooted, free e loro equivalenza), spanning tree/forest.
    • Proprietà dei grafi: Proposizioni 14.8, 14.10, 14.11 ed esercizio C-14.34 del testo.
    • Rappresentazione di grafi: strutture di base L_E e L_V; liste di adiacenza; matrice di adiacenza.

    Lezione 27: 02/12/25

    • Visite (traversal): nozione di visita.
    • Algoritmo BFS: pseudocodice; esempio; proprietà; analisi di complessità; estensione della visita a tutto il grafo.

    Lezione 28: 03/12/25

    • Applicazioni della BFS: connettività, spanning tree, cammini minimi, ciclicità.
    • Algoritmo DFS:  pseudocodice; esempio; proprietà; analisi di complessità.
     
    Lezione 29: 04/12/25
     
    • Algoritmo DFS:  proprietà; analisi di complessità.
    • Esercizi: algoritmo ReachablePairs (Slide 82 - Parte 1); MaxSeparation (Slide 24 e 90 - Parte 1); IsBipartite (Slide 90, secondo esercizio - Parte 1).

    Lezione 30: 09/12/25
     
    • Esercizi: algoritmo IsBipartite (Slide 90, secondo esercizio - Parte 1); esercizio dalla Slide 87 - Parte 1.
    • Cammini minimi pesati: definizioni di grafo pesato, lunghezza di un cammino, e cammino minimo; proprietà dei cammini minimi; 
    • Problema dei Single-Source Shortest  Paths (SSSP).
    • Algoritmo di Dijkstra: strategia ad alto livello e pseudocodice; esempio.

    Lezione 31: 10/12/25 
     
    • Algoritmo di Dijkstra: analisi di correttezza; analisi di complessità implementando Q con Heap, Lista (e con Fibonacci Heap ma senza prova).
    • Grafi Diretti: terminologia (grado uscente/entrante, cammino/ciclo diretto, vertici raggiungibili da un vertice v, versione non diretta di un grafo diretto, nozione di grafo fortemente/debolmente connesso); proprietà relative alla somma dei gradi uscenti/entranti; rappresentazione tramite liste di adiacenza.
    • BFS e DFS di grafi diretti: esempi 

    Lezione 32: 11/12/25
     
    • BFS e DFS di grafi diretti: complessità e proprietà.
    • Esercizio: identificazione dei BACK EDGE nella DFS diretta (Slide 67 - Parte 2).
    • Grafi diretti aciclici (DAG=Directed Acyclic Graph): definizione e ordinamento topologico.
    • Algoritmo TopologicalSort(G): esempio; analisi di di complessità.
    • Esercizio:  identificazione di un ciclo in un grafo diretto (Primo esercizio di Slide 75 - Parte 2) 
     
    Lezione 33: 16/12/25
     
    • Esercizi: modifica di ShortestPaths per grafi non connessi (Slide 42 - Parte 2);  trasformazione di un grafo non diretto in un DAG (terzo esercizio Slide 92 - Parte 2); scheduling di task tramite TopologicalSort (Slide 93 - Parte 2).

    Materiale: