- Attuale
- In coda
- Visitato
- Percorso
Visita in ampiezza (BFS)
La visita in ampiezza esplora un grafo ad anelli: prima ogni nodo vicino alla partenza, poi ogni nodo a due archi di distanza, e così via. Lo fa con una coda: il primo che entra è il primo che esce. Fai clic su un nodo per partire da lì, scegli un arrivo se vuoi, e procedi passo per passo per vedere la coda crescere e calare, ogni nodo ricevere la sua distanza e comparire un percorso più breve. Premi Avvia per guardare la visita, oppure Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare dove vuoi. Fai clic su un nodo per farne la partenza; passa il clic su Arrivo e fai clic su un altro nodo per cercare un percorso più breve fino a lì. Il numero su ogni nodo è la sua distanza dalla partenza, e la riga sotto il grafo è la coda. Nuovo grafo crea un altro grafo; scegli quanti nodi e archi deve avere. Con il riquadro selezionato, le frecce vanno avanti e indietro di un passo, la barra spaziatrice avvia e mette in pausa, e Home e Fine saltano all'inizio e alla fine.
Come funziona
- Fai clic su un nodo per farne la partenza. Per cercare un percorso, passa il clic su Arrivo e fai clic su un altro nodo.
- Premi Avvia, oppure usa Passo e Indietro per procedere un passo alla volta. Trascina il cursore dei passi per saltare in qualsiasi punto della visita.
- Osserva la coda sotto il grafo e la distanza su ogni nodo. Nuovo grafo crea un altro grafo da provare.
Come funziona la visita in ampiezza
Metti il nodo di partenza in una coda con distanza 0. Poi ripeti: prendi il nodo in testa alla coda ed esamina ciascuno dei suoi vicini. Un vicino non ancora visto riceve una distanza più alta di uno rispetto al nodo preso, ricorda quel nodo come quello da cui è stato raggiunto ed entra in fondo alla coda. I vicini già visti vengono saltati. Quando la coda è vuota, ogni nodo raggiungibile ha la sua distanza.
Perché trova i percorsi più brevi
La coda restituisce i nodi nell'ordine in cui sono stati trovati, e i nodi vengono trovati anello per anello: tutti i nodi a distanza 1 entrano in coda prima di quelli a distanza 2, e così via. Quindi, la prima volta che un nodo viene raggiunto, lo è tramite un percorso con il minor numero possibile di archi. Risalendo i nodi ricordati dall'arrivo alla partenza si ottiene quel percorso. Contano solo gli archi; quando gli archi hanno lunghezze diverse, serve l'algoritmo di Dijkstra.
Domande frequenti
Che cos'è la visita in ampiezza?
Un modo per esplorare un grafo da un nodo di partenza visitando prima tutti i suoi vicini, poi i loro vicini, e così via, anello per anello. Usa una coda per tenere i nodi nell'ordine in cui sono stati trovati.
La visita in ampiezza trova il percorso più breve?
Sì, quando ogni arco conta allo stesso modo: la prima volta che la BFS raggiunge un nodo, ha usato il minor numero possibile di archi. Per archi di lunghezze diverse, usa invece l'algoritmo di Dijkstra.
Qual è la differenza tra BFS e DFS?
La visita in ampiezza usa una coda e si allarga in modo uniforme, anello per anello. La visita in profondità usa una pila (o la ricorsione) e segue un percorso il più a fondo possibile prima di tornare indietro. La BFS trova i percorsi più brevi in archi; la DFS no, ma è utile per trovare cicli e per l'ordinamento topologico.
Quanto è veloce la visita in ampiezza?
Toglie ogni nodo dalla coda una volta ed esamina ogni arco da entrambe le estremità, quindi il lavoro cresce con il numero di nodi più il numero di archi.
Il mio grafo viene inviato da qualche parte?
No. Il grafo viene creato e visitato nel tuo browser, e le tue ultime impostazioni restano nella memoria locale di questo browser.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Vai all'editor