cerca
Algoritmi e strutture dati - Esplorazione di un grafo non orientato
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

Algoritmi e strutture dati - Esplorazione di un grafo non orientato

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