Riki Chardo
Apprendista Forumista
 Offline
Gender: 
Posts: 101
r36tig89tgcj
|
 |
« Reply #112 on: 10-10-2010, 19:01:20 » |
|
ma non devi disegnare proprio nnt...
Sia dato un grafo G = (V, E) non direzionato contenente 5 nodi e descritto dalla seguente definizione insiemistica
V = {v0, v1, v2, v3, v4}
E = {(v0, v3), (v1, v2), (v1, v3), (v1, v4), (v3, v4)}
Si fornisca la corretta sequenza di nodi scoperti dalla chiamata di procedura DFS(G).
Allora DFS partiamo da v0
Quindi v0 _ _ _ _
Il primo arco incidente in v0
E = {(v0, v3), (v1, v2), (v1, v3), (v1, v4), (v3, v4)}
Quindi v0 v3_ _ _
dopodicche il primo arco incidente in v3 se esiste altrimenti si torna a v0
E = {(v0, v3), (v1, v2), (v1, v3), (v1, v4), (v3, v4)}
poiche v0 è gia visitato si passa al prossimo arco in v3. Ricorda sempre che se finiscono gli archi si torna indietro a v0
E = {(v0, v3), (v1, v2), (v1, v3), (v1, v4), (v3, v4)}
Quindi v0 v3 v1 _ _
il primo arco incidente in v1
E = {(v0, v3), (v1, v2), (v1, v3), (v1, v4), (v3, v4)}
Quindi v0 v3 v1 v2 _
Cosa resta ? v4
v0 v3 v1 v2 v4
BFS
ia dato un grafo G = (V, E) non direzionato contenente 5 nodi e descritto dalla seguente lista di adiacenza
[v0]-->(v1)-->null
[v1]-->(v0)-->(v2)-->(v4)-->null
[v2]-->(v1)-->(v3)-->null
[v3]-->(v2)-->(v4)-->null
[v4]-->(v1)-->(v3)-->null
Si fornisca la corretta sequenza di nodi scoperti dalla chiamata di procedura BFS(G, v1).
Si parte dunque da v1
v1_ _ _ _
Continuare inserendo, in ordine, tutti i nodi presenti nella lista di adiacenza di v1...
v1 v0 v2 v4 _
Si continua inserendo, in ordine, tutti i nodi presenti nella lista di adiacenza di v0,poi v2... v4 .. ecc
Ma in qst caso cosa resta?
v3
quindi
v1 v0 v2 v4 v3
Ti svolgo allo stesso modo altri due esempi, ho cercato quelli con il maggior numero di casi possibile.
Sia dato un grafo G = (V, E) non direzionato contenente 7 nodi e descritto dalla seguente definizione insiemistica
V = {v0, v1, v2, v3, v4, v5, v6}
E = {(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
Si fornisca la corretta sequenza di nodi scoperti dalla chiamata di procedura DFS(G).
Cominciamo
v0 _ _ _ _ _ _
cerchiamo primo nodo adiacente a v0
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v2
v0 v2 _ _ _ _ _
cerchiamo primo nodo adiacente a v2
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
poichè v0 è gia visitato passiamo al prossimo nodo adiacente a v2
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v1
v0 v2 v1 _ _ _ _
cerchiamo primo nodo adiacente a v1
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v2 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
Non c'è altro nodo adiacente a v1 si torna a v2
v0 v2 v1 _ _ _ _
prossimo nodo adiacente a v2
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v0 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v2 gia visitato .. prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v3
v0 v2 v1 v3 _ _ _
prossimo nodo adiacente a v3
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v2 gia visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v6
v0 v2 v1 v3 v6 _ _
prossimmo nodo adiacente a v6
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v0 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v3 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
non ci sono altri nodo adiacenti si torna a v3
v0 v2 v1 v3 v6 _ _
prossimo nodo adiacente a v3
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v2 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v6 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
non ci sono altri nodi adiacenti torniamo a v1
v0 v2 v1 v3 v6 _ _
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v2 gia visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
non ci sono altri nodi adiacenti a v1 torniamo a v2
v0 v2 v1 v3 v6 _ _
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v0 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v1 già visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v3 gia visitato prossimo
{(v0, v2), (v0, v4), (v0, v6), (v1, v2), (v2, v3), (v2, v5), (v3, v6), (v4, v5)}
v5
quindi
v0 v2 v1 v3 v6 v5 _
Siamo ad uno dalla fine.. ki non è stato ancora visitato? v4
v0 v2 v1 v3 v6 v5 v4
Chiaramente nella tua mente perdi pochissimo tempo soprattutto allenandoti.. e poi il 70% di tutti questi passaggi possono benissimo essere saltati xke a volte riprendi le visite da dv avevi gia smesso prima senza ricominciare da capo. diventerà una cosa automatica e veloce anke nel caso peggiore che è proprio questo.
BFS
Sia dato un grafo G = (V, E) non direzionato contenente 7 nodi e descritto dalla seguente definizione insiemistica
V = {v0, v1, v2, v3, v4, v5, v6}
E = {(v0, v1), (v0, v4), (v1, v2), (v1, v3), (v1, v4), (v1, v6), (v3, v4), (v3, v6), (v4, v5), (v5, v6)}
Si fornisca la corretta sequenza di nodi scoperti dalla chiamata di procedura BFS(G, v3).
cominciamo dunque da v3
v3 _ _ _ _ _ _
Scorriamo la lista di adiacenza di v3 aggiungendo, in ordine, i nodi non ancora visitati.
{(v0, v1), (v0, v4), (v1, v2), (v1, v3), (v1, v4), (v1, v6), (v3, v4), (v3, v6), (v4, v5), (v5, v6)}
v3 v1 v4 v6 _ _ _
continuiamo con v1
{(v0, v1), (v0, v4), (v1, v2), (v1, v3), (v1, v4), (v1, v6), (v3, v4), (v3, v6), (v4, v5), (v5, v6)}
v3 v1 v4 v6 v0 v2 _
manca v5 da visitare
v3 v1 v4 v6 v0 v2 v5
La BFS è sempre quasi immediata... Buona fortuna.
|
