Uni.EsplorazioneDiUnGrafoNonOrientato History

Show minor edits - Show changes to markup

November 28, 2007, at 04:39 PM by Ido -
Changed lines 7-8 from:
to:
Restore
November 28, 2007, at 04:37 PM by Ido -
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)

Restore
November 28, 2007, at 04:37 PM by Ido -
Added lines 1-6:

(:title Algoritmi e strutture dati - Esplorazione di un grafo non orientato:) Torna alla pagina di Algoritmi e strutture dati 

 :: 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

Restore
November 06, 2007, at 07:18 PM by MiTicozzo -
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.

Restore
November 06, 2007, at 07:11 PM by MiTicozzo -
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)

Restore
November 06, 2007, at 07:03 PM by MiTicozzo -
Changed lines 1-5 from:
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)

Restore
November 06, 2007, at 06:56 PM by MiTicozzo -
Added line 1:
Restore