|
Wiki
UniCrema
Materie per semestre
Materie per anno
Materie per laurea
Help
|
|
Uni.EsplorazioneDiUnGrafo History
Hide minor edits - Show changes to output
Changed line 1 from:
(:title Algoritmi e strutture dati - Esplorazione di un grafo:) to:
(:title Algoritmi e strutture dati - Esplorazione di un grafo orientato:) Changed lines 5-6 from:
%titolo%''':: Esplorazione di un grafo ::''' to:
%titolo%''':: Esplorazione di un grafo orientato ::'''
Added lines 1-6:
(:title Algoritmi e strutture dati - Esplorazione di un grafo:)
[[Torna alla pagina di Algoritmi e strutture dati->Uni.Algoritmi]]
----
%titolo%''':: Esplorazione di un grafo ::''' Changed lines 11-12 from:
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.\\ to:
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. Changed lines 14-17 from:
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. to:
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->Uni.Algoritmi]]
Changed lines 7-8 from:
'''BFS:''''''1'''(1,2)(1,4)'''2'''(2,3)(2,5)'''4'''(4,2)(4,3)'''3'''(3,1)'''5'''(5,3)(5,4) to:
'''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.
Changed lines 6-7 from:
to:
'''BFS:''''''1'''(1,2)(1,4)'''2'''(2,3)(2,5)'''4'''(4,2)(4,3)'''3'''(3,1)'''5'''(5,3)(5,4)
Changed lines 5-6 from:
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.\\ to:
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:'''
Changed line 5 from:
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.\\\ to:
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.\\
Changed lines 4-5 from:
'''DFS:''''''1'''(1,2)'''2'''(2,3)'''3'''(3,1)(2,5)'''5'''(5,3)(5,4)'''4'''(4,2)(4,3)(1,4) to:
'''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.\\\
Changed lines 1-4 from:
to:
Attach:grafo.jpg\\
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)
|
|
