Torna alla pagina di Algoritmi e strutture dati
:: Esplorazione di un grafo non orientato::
Le cose non cambiano di molto se il grafo non è orientato. La differenza sta che non abbiamo più un percorso obbligato. Mostriamo subito le vistite:
DFS: 1(1,2) 2(2,1)(2,3) 3(3,2)(3,6) 6(6,1)(6,2)(6,3) 2(2,5) 5(5,1)(5,2)(5,4) 4(4,1)(4,5)(4,7) 7(7,4)(7,5)(1,4)(1,5)(1,6).
La differenza dov'è? E' che visitato il nodo 2 non ho alcuna freccia che mi forzi il percorso, quindi posso benissimo rivisitare l'arco (2,1) senza conseguenze, dato che il nodo 1 è stato già visitato. Per il resto il procedimento è uguale a quello di una vistita DFS per un grafo orientato.
BFS: 1(1,2)(1,4)(1,5)(1,6) 2(2,1)(2,3)(2,5)(2,6) 4(4,1)(4,5)(4,7) 5(5,1)(5,2)(5,4)(5,7) 6(6,1)(6,2)(6,3) 3(3,2)(3,6) 7(7,4)(7,5)
Torna alla pagina di Algoritmi e strutture dati
