Uni.EsplorazioneDiUnGrafoNonOrientato History
Hide minor edits - Show changes to output
Changed line 12 from:
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 DSS per un grafo orientato.\\ to:
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.\\
Changed lines 7-8 from:
to:
Changed lines 10-11 from:
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). to:
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). Changed lines 14-16 from:
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)
Lo stesso vale per la BFS. to:
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)
Added lines 1-6:
(:title Algoritmi e strutture dati - Esplorazione di un grafo non orientato:)
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
----
%titolo%''':: Esplorazione di un grafo non orientato::''' Changed lines 8-12 from:
[[<<]]
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).\\
to:
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). Changed lines 14-15 from:
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)\\
Lo stesso vale per la BFS. to:
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)
Lo stesso vale per la BFS.
----
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
Changed lines 5-6 from:
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).\\
to:
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).\\ Changed lines 8-10 from:
'''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) to:
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)\\
Lo stesso vale per la BFS.
Changed lines 5-7 from:
'''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) to:
'''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 DSS 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)
Changed lines 1-5 from:
to:
Attach:grago2.jpg
[[<<]]
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)
|
