Torna alla pagina di Algoritmi e strutture dati

 :: Esplorazione di un grafo orientato ::

Un esercizio potrebbe essere questo, ovvero: "Dato un grafo orientato, mostrare l'ordine di visita per DFS e BFS."

Dunque, noi sappiamo che l'ordine di visita DFS dopo aver visitato un nodo u si allontana più possibile da esso, visitando i nodi successivi fino a quando non arriva ad un vicolo cieco. Arrivato a questo punto torno lungo l'ultimo arco visitato e riparto. Ritornando all'esercizio l'ordine di visita DFS sarà:
DFS:1(1,2)2(2,3)3(3,1)(2,5)5(5,3)(5,4)4(4,2)(4,3)(1,4).
L'idea di fondo è: parto dal nodo e inizio a visitare l'arco, se arrivo in un nodo non visitato lo visito. Altrimenti se con l'esame dell'arco arrivo in un nodo già visitato torno indietro all'ultimo nodo visitato e da qui continuo gli esami degli archi. Ad esempio, nell'esercizio arrivato al nodo 3 analizzo l'arco (3,1), dato che il nodo 1 l'ho già visitato torno indietro. A questo punto vedo che il nodo 3 non ha più archi uscenti quindi torno ancora indietro fino ad arrivare al nodo 2. Da qui proseguo l'analisi degli archi.

BFS:1(1,2)(1,4)2(2,3)(2,5)4(4,2)(4,3)3(3,1)5(5,3)(5,4)
Qui la storia cambia, partiamo visitando il nodo 1 e visitiamo tutti gli archi che escono da lui, quindi (1,2) e (1,4). E ora dove andiamo? Andiamo al nodo più piccolo quindi 2, e facciamo la visita per tutti gli archi che escono dal nodo 2. Verrebbe da dire che ora si va al nodo 3, sbagliato! La definizione dice: i nodi sono visitati in odine di distanza crescente dal nodo di partenza. Ciò non vuol dire che devo ordinare i nodi, ma se ho visitato il nodo 2, ora devo passare al 4 che è quello immediatamente dopo al nodo 2. Quando incontro un nodo visitato lo salto e vado a quello successivo non visitato. Così via, fino alla fine.

Torna alla pagina di Algoritmi e strutture dati