Pages: 1 ... 7 8 [9]   Go Down
Print
Author Topic: Risultati esami  (Read 17085 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #120 on: 11-10-2010, 18:17:08 »

Ok grazie mille....c'è però ancora un tipo che sbaglio.

Quote
Sia dato un grafo G = (V, E) non direzionato contenente 7 nodi e descritto dalla seguente lista di adiacenza
[v0]-->(v1)-->(v2)-->(v3)-->null
[v1]-->(v0)-->(v2)-->(v4)-->(v6)-->null
[v2]-->(v0)-->(v1)-->(v5)-->(v6)-->null
[v3]-->(v0)-->(v4)-->(v5)-->(v6)-->null
[v4]-->(v1)-->(v3)-->null
[v5]-->(v2)-->(v3)-->null
[v6]-->(v1)-->(v2)-->(v3)-->null


Si fornisca la corretta sequenza di nodi scoperti dalla chiamata di procedura DFS(G).

Quando ho la lista di adiacenza sbaglio.....parto sempre da v0 e poi come faccio a capire quanti ne devo visitare di adiacenti?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
dani89
Apprendista Forumista
**
Offline Offline

Posts: 254



« Reply #121 on: 11-10-2010, 19:05:47 »

nella DFS devi visitare il primo (in questi esercizi del prof l'ordine è: v0 v1 v2. ........ vn) e poi passare alla lista di adiacenza del primo nodo adiacente e così via fino a che non li hai visitati tutti.
Logged
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #122 on: 11-10-2010, 19:56:33 »

nella DFS devi visitare il primo (in questi esercizi del prof l'ordine è: v0 v1 v2. ........ vn) e poi passare alla lista di adiacenza del primo nodo adiacente e così via fino a che non li hai visitati tutti.

Esatto in questo caso
partiamo da v0
il primo nodo adiacente a v0 è v1
quindi
v0 v1 _ _ _ _ _
quindi passiamo alla lista di adiacenza di v1.. ed il primo nodo adiacente è v0 ke è già stato visitato quindi il prossimo adiacente a v1 è v2

v0 v1 v2 _ _ _ _

lista di adiacenza di v2
[v2]-->(v0)-->(v1)-->(v5)-->(v6)-->null

v0 visitato, v1 visitato quindi visitiamo v5

v0 v1 v2 v5 _ _ _

lista di v5
[v5]-->(v2)-->(v3)-->null

v2 visitato visitiamo v3

v0 v1 v2 v5 v3 _ _

lista di v3

[v3]-->(v0)-->(v4)-->(v5)-->(v6)-->null

v0 già visitato quindi v4

v0 v1 v2 v5 v3 v4 _

l'ultimo è v6

v0 v1 v2 v5 v3 v4 v6
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #123 on: 11-10-2010, 20:16:20 »

Scusate, forse ho inteso male io, ma mi sembra che in questo modo, confrontando lo svolgimento di BFS e DFS siano uguali così.....
Se per esempio prendo:

Code:
Sia dato un grafo G = (V, E) non direzionato contenente 7 nodi e descritto dalla seguente lista di adiacenza
[v0]-->(v1)-->(v3)-->(v4)-->null
[v1]-->(v0)-->(v5)-->null
[v2]-->(v5)-->null
[v3]-->(v0)-->(v6)-->null
[v4]-->(v0)-->(v5)-->(v6)-->null
[v5]-->(v1)-->(v2)-->(v4)-->(v6)-->null
[v6]-->(v3)-->(v4)-->(v5)-->null


Si fornisca la corretta sequenza di nodi scoperti dalla chiamata di procedura DFS(G).

Il mio output è:

Code:
v0 v1 v3 v4 v5 v6 v2

Secondo il sistema no.....
Ma così non ho preso tutti i nodi adiacenti alle varie liste?
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #124 on: 11-10-2010, 20:37:45 »

Scusate, forse ho inteso male io, ma mi sembra che in questo modo, confrontando lo svolgimento di BFS e DFS siano uguali così.....
Se per esempio prendo:

Code:
Sia dato un grafo G = (V, E) non direzionato contenente 7 nodi e descritto dalla seguente lista di adiacenza
[v0]-->(v1)-->(v3)-->(v4)-->null
[v1]-->(v0)-->(v5)-->null
[v2]-->(v5)-->null
[v3]-->(v0)-->(v6)-->null
[v4]-->(v0)-->(v5)-->(v6)-->null
[v5]-->(v1)-->(v2)-->(v4)-->(v6)-->null
[v6]-->(v3)-->(v4)-->(v5)-->null


Si fornisca la corretta sequenza di nodi scoperti dalla chiamata di procedura DFS(G).

Il mio output è:

Code:
v0 v1 v3 v4 v5 v6 v2

Secondo il sistema no.....
Ma così non ho preso tutti i nodi adiacenti alle varie liste?

no quello ke hai fatto tu è la bfs in v0

ci siamo capiti male tu parti da v0 inserisci v1 e poi devi passare alla lista di adiacenza di v1 e quindi prendere il primo non visitato ke è v5
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #125 on: 11-10-2010, 21:01:38 »

 no

Ti ringrazio tanto. 
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #126 on: 11-10-2010, 21:55:11 »

no

Ti ringrazio tanto. 

Di nnt ma... sicuro di aver capito?
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #127 on: 11-10-2010, 22:14:51 »

Si, domani mattina mi alzo presto e provo a fare qualche esercizio.

Praticamente se c'è il BFS, devo leggere la lista di adicenza per ogni nodo, da v0 a vn.
Invece per il DFS parto da v0, leggo il primo nodo nella lista di adiazenza, ad esempio v1, e poi passa alla lista di v1, e mi comporto in base ai nodi che ho già visitato o meno.
Spero di non sbagliare.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Riki Chardo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 101


r36tig89tgcj


« Reply #128 on: 11-10-2010, 22:36:08 »

no... per bfs parti da quello preso come parametro e poi continui in base alla lista ke ti si crea come risultato  per la dfs giusto e ricorda ke se ti finiscono i nodi adiacenti del tipo se gia risultano tutti visitati allora torni al nodo di prima.
Buona fortuna! a dmn
Logged
Pages: 1 ... 7 8 [9]   Go Up
Print
Jump to: