Visita in Ampiezza (BFS)

1. Cos'è la Visita in Ampiezza (Breadth-First Search)?

La BFS (Breadth-First Search) è un algoritmo di attraversamento e ricerca in un grafo che esplora i nodi procedendo per strati concentrici (o livelli). Partendo da un vertice sorgente $s$, l'algoritmo visita prima tutti i vicini diretti (distanza 1), poi i vicini dei vicini (distanza 2) e così via, prima di approfondire ulteriormente la ricerca.

A differenza della DFS che utilizza una pila (o la ricorsione), la BFS richiede tassativamente una struttura dati di tipo Coda (Queue) che opera secondo la politica FIFO (First In, First Out), garantendo l'ordine corretto di visita per livelli.

2. Proprietà e Complessità

Cammino Minimo: Nei grafi non pesati, la BFS garantisce sempre il ritrovamento del cammino minimo (in termini di numero di archi) tra la sorgente e qualsiasi altro nodo raggiungibile.
Complessità Temporale $\mathcal{O}(V + E)$: Utilizzando una lista di adiacenza, ciascun vertice ($V$) viene inserito/estratto dalla coda una volta e ciascun arco ($E$) viene esaminato.
Complessità Spaziale $\mathcal{O}(V)$: Lo spazio è dominato dalla coda e dal vettore booleano di marcatura dei nodi visitati, che nel caso peggiore (grafo con un unico grande livello) possono contenere tutti i vertici.

                // Implementazione BFS in C++ con std::vector e std::queue
                #include <vector>
                #include <queue>
                #include <iostream>

                void bfs(int startNode, const std::vector<std::vector<int>>& adjList) {
                int n = adjList.size();
                std::vector<bool> visited(n, false);
                std::queue<int> q;

                visited[startNode] = true;
                q.push(startNode);

                while (!q.empty()) {
                int curr = q.front();
                q.pop();
                std::cout << curr << " ";

                for (int neighbor :
                adjList[curr]) {
                if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
                }
                }
                }
                }
            

3. Simulatore Interattivo: Configurazione Esplorazione BFS

Simula i parametri operativi dell'attraversamento BFS inserendo il numero di vertici del grafo e il nodo di partenza.

bfs-engine@nexus-core:~# Breadth-First Simulation

Nodi Totali ($V$):

Nodo Sorgente ($s$):

> Inserisci i parametri e avvia la simulazione della struttura di coda FIFO.

1. Cos'è la Visita in Ampiezza (Breadth-First Search)?

2. Proprietà e Complessità

3. Simulatore Interattivo: Configurazione Esplorazione BFS

Gestione della Privacy e dei Cookie