Attraversamento grafico
Attraversamento grafico significa visitare ogni vertice e bordo esattamente una volta in un pozzo -ordine definito. Durante lutilizzo di determinati algoritmi del grafico, è necessario assicurarsi che ogni vertice del grafico venga visitato esattamente una volta. Lordine in cui i vertici vengono visitati è importante e può dipendere dallalgoritmo o dalla domanda che stai risolvendo.
Durante un attraversamento, è importante tenere traccia di quali vertici sono stati visitati. Il modo più comune per tracciare i vertici è contrassegnarli.
Breadth First Search (BFS)
Ci sono molti modi per attraversare i grafici. BFS è lapproccio più comunemente utilizzato.
BFS è un algoritmo di attraversamento in cui dovresti iniziare ad attraversare da un nodo selezionato (sorgente o nodo di partenza) e attraversare il grafico a livello esplorando così i nodi vicini (nodi che sono direttamente collegati al nodo di origine). Devi quindi muoverti verso i nodi vicini di livello successivo.
Come suggerisce il nome BFS, ti viene richiesto di attraversare il grafico in larghezza come segue:
- Prima muovi orizzontalmente e visita tutti i nodi del livello corrente
- Passa al livello successivo
Considera il seguente diagramma. 
La distanza tra i nodi nel livello 1 è comparativamente minore della distanza tra i nodi nel livello 2. Pertanto, in BFS, è necessario attraversare tutti i nodi nel livello 1 prima di passare ai nodi nel livello 2.
Attraversare i nodi figli
Un grafico può contenere cicli, che possono portarti di nuovo allo stesso nodo mentre attraversi il grafico. Per evitare di elaborare nuovamente lo stesso nodo, utilizzare un array booleano che contrassegna il nodo dopo che è stato elaborato. Mentre visiti i nodi nel livello di un grafico, memorizzali in modo tale da poter attraversare i nodi figlio corrispondenti in un ordine simile.
Per rendere questo processo facile, utilizzare una coda per memorizzare il nodo e contrassegnarlo come “visitato” fino a quando tutti i suoi vicini (vertici che sono direttamente collegati ad esso) sono contrassegnati. La coda segue il metodo di accodamento First In First Out (FIFO), quindi i vicini del nodo verranno visitati nellordine in cui sono stati inseriti nel nodo ovvero verrà visitato per primo il nodo che è stato inserito per primo, quindi su.
Pseudocodice
Processo di attraversamento 
Il traversamento partirà dal nodo di origine e metterà in coda i messaggi di posta elettronica. verranno contrassegnati come “visitati”.
La prima iterazione
- i s verranno estratti dalla coda
- I vicini di s ie 1 e 2 verranno attraversati
- 1 e 2, che non sono stati attraversati in precedenza, vengono attraversati. Saranno:
- Inseriti in coda
- 1 e 2 saranno contrassegnati come visitati
Seconda iterazione
- 1 viene estratto dalla coda
- I vicini di 1 cioè se vengono attraversati e 3 vengono attraversati
- vengono ignorati perché contrassegnati come “visitati”
- 3, che non è stato attraversato in precedenza, viene attraversato. È:
- Inserito in coda
- Contrassegnato come visitato
Terza iterazione
- 2 viene estratto dalla coda
- I vicini di 2 cioè s, 3 e 4 vengono attraversati
- 3 e vengono ignorati perché contrassegnati come “visitati”
- 4, che non è stato attraversato in precedenza, viene attraversato. È:
- Inserito in coda
- Contrassegnato come visitato
Quarta iterazione
- 3 viene estratto dalla coda
- I vicini di 3, cioè 1, 2 e 5 vengono attraversati
- 1 e 2 vengono ignorati perché contrassegnati come “visitati”
- 5, che non è stato attraversato in precedenza, viene attraversato. È:
- Inserito in coda
- Contrassegnato come visitato
Quinta iterazione
- 4 verrà estratto dalla coda
- Vicini di 4 cioè 2 viene attraversato
- 2 viene ignorato perché è già contrassegnato come “visitato”
Sesta iterazione
- 5 viene estratto dalla coda
- Vicini di 5 cioè 3 viene attraversato
- 3 viene ignorato perché è già contrassegnata come “visitata”
La coda è vuota e esce dal ciclo. Tutti i nodi sono stati attraversati utilizzando BFS.
Se tutti i bordi in un grafico hanno lo stesso peso, allora BFS può essere utilizzato anche per trovare la distanza minima tra i nodi in un grafico.
Esempio
Come in questo diagramma, inizia dal nodo sorgente, per trovare la distanza tra la sorgente nodo e nodo 1. Se non segui lalgoritmo BFS, puoi andare dal nodo sorgente al nodo 2 e quindi al nodo 1. Questo approccio calcolerà la distanza tra il nodo sorgente e il nodo 1 come 2, mentre il minimo la distanza è effettivamente 1. La distanza minima può essere calcolata correttamente utilizzando lalgoritmo BFS.
Complessità
La complessità temporale di BFS è O (V + E), dove V è il numero di nodi ed E è il numero di archi.
Applicazioni
1. Come determinare il livello di ogni nodo nellalbero dato?
Come sai in BFS, attraversi il livello in modo saggio. È inoltre possibile utilizzare BFS per determinare il livello di ogni nodo.
Implementazione
Questo codice è simile al codice BFS con solo la seguente differenza:
level] = level + 1;
In questo codice, mentre visiti ogni nodo, il livello di quel nodo viene impostato con un incremento del livello del suo nodo padre. Questo è il modo in cui viene determinato il livello di ogni nodo.
2 . 0-1 BFS
Questo tipo di BFS viene utilizzato per trovare la distanza più breve tra due nodi in un grafico a condizione che i bordi nel grafico abbiano i pesi 0 o 1. Se si applica il BFS spiegato in precedenza in in questo articolo, otterrai un risultato errato per la distanza ottimale tra 2 nodi.
In questo approccio, un array booleano non viene utilizzato per contrassegnare il nodo perché la condizione della distanza ottimale verrà verificata quando tu visita ogni nodo. Una coda a doppia estremità viene utilizzata per memorizzare il nodo. In 0-1 BFS, se il peso del bordo = 0, il nodo viene spinto davanti al dequeue. Se il peso del bordo = 1, il nodo viene spinto sul retro della coda.
Implementazione
Q è una coda a doppia estremità. La distanza è un array in cui, distanza conterrà la distanza dal nodo iniziale al nodo v. Inizialmente la distanza definita dal nodo sorgente a ciascun nodo è infinita.
Comprendiamo questo codice con il seguente grafico:
Lelenco di adiacenze del grafico sarà il seguente:
Qui “s” è considerato 0 o nodo sorgente.
0 – > 1 – > 3 – > 2
bordi.first = 1, bordi.second = 1
bordi.first = 3, bordi.second = 0
edge.first = 2, bordi.second = 1
1 – > 0 – > 4
edge.first = 0, edge.second = 1
edge.first = 4 , edge.second = 0
2 – > 0 – > 3
edge.first = 0 , edge.second = 0
edge.first = 3, edge.second = 0
3 – > 0 – > 2 – > 4
edge.first = 0, edge.second = 0
edge.first = 2, edge.second = 0
bordi.first = 4, bordi.second = 0
4 – > 1 – > 3
bordi.first = 1, bordi.second = 0
bordi.first = 3, bordi.second = 0
Se usi lalgoritmo BFS, il risultato non sarà corretto perché ti mostrerà la distanza ottimale tra s e il nodo 1 es e il nodo 2 come 1 rispettivamente. Questo perché visita i figli di se calcola la distanza tra se i suoi figli, che è 1. La distanza ottimale effettiva è 0 in entrambi i casi.
Elaborazione
Partendo dal nodo sorgente, cioè 0, si sposterà verso 1, 2 e 3. Poiché il peso del bordo tra 0 e 1 e 0 e 2 è rispettivamente 1 , 1 e 2 verranno spostati in fondo alla coda. Tuttavia, poiché il peso del bordo compreso tra 0 e 3 è 0, 3 verrà spostato in primo piano nella coda. La distanza verrà mantenuta di conseguenza nellarray di distanza.
3 verrà quindi estratto dalla coda e lo stesso processo verrà applicato ai suoi vicini, e così via.