Teoria e Algoritmi sui Grafi

1. Introduzione e Modelli di Rappresentazione

Un grafo $G = (V, E)$ è costituito da un insieme di vertici (o nodi) $V$ e da un insieme di archi $E$ che collegano coppie di vertici. I grafi possono essere orientati (direzionati) o non orientati, pesati o non pesati. Le due tecniche principali per memorizzare un grafo in memoria sono:

Matrice di Adiacenza: Una matrice bidimensionale di dimensione $V \times V$ dove l'elemento $M[i][j] = 1$ (o pari al peso) indica la presenza di un arco tra il nodo $i$ e il nodo $j$. Ottimale per grafi densi ($\mathcal{O}(V^2)$ spazio).
Liste di Adiacenza: Un array o vettore di liste concatenate, dove ciascun nodo memorizza la lista dei propri adiacenti. Ideale per grafi sparsi ($\mathcal{O}(V + E)$ spazio).

                // Esempio di struttura per Lista di Adiacenza in C++
                #include <vector>
                #include <list>

                class Graph {
                int V;
                std::vector<std::list<int>> adjList;
                public:
                Graph(int v) : V(v), adjList(v) {}

                void addEdge(int u, int v) {
                adjList[u].push_back(v);
                adjList[v].push_back(u); // Se non orientato
                }
                };
            

2. Algoritmi di Visita: BFS e DFS

L'attraversamento sistematico di un grafo permette di esplorare i componenti connessi e trovare percorsi:

DFS (Depth-First Search): Esplora in profondità sfruttando un approccio ricorsivo o uno Stack esplicito. Segna i nodi visitati per evitare cicli infiniti.
BFS (Breadth-First Search): Esplora per livelli a partire da un nodo sorgente, utilizzando una Coda (Queue). Trova il cammino minimo in termini di numero di archi nei grafi non pesati.

Complessità Computazionale:

Sia con Liste di Adiacenza: $\mathcal{O}(V + E)$
Sia per DFS che per BFS, ogni vertice e arco viene esaminato al massimo un numero costante di volte.

3. Simulatore Interattivo: Visita del Grafo

Seleziona l'algoritmo di esplorazione applicato al grafo campione di test ($V = 5$ nodi).

graph-engine@nexus-core:~# Graph Traversal Simulator

Strategia di Visita:

Azione:

> Grafo di test caricato: Nodi [0, 1, 2, 3, 4] con archi collegati. Seleziona l'algoritmo e avvia la simulazione.

Teoria e Algoritmi sui Grafi

1. Introduzione e Modelli di Rappresentazione

2. Algoritmi di Visita: BFS e DFS

3. Simulatore Interattivo: Visita del Grafo

Gestione della Privacy e dei Cookie