[Algoritmi]Chiarimento visita BFS sui grafi
Ciao!
Volevo porvi una domanda sulla visita BFS su di un grafo. Quando devo considerare gli archi che incidono su un nodo u,estratto dalla coda, non ho capito se devo considerarli in un ordine specifico oppure posso procedere arbitrariamente?Cerco di spiegarmi con un esempio:
In questo grafo voglio applicare BFS(G,s), ora dalla coda estraggo s poi considero prima l'arco(s,r) oppure l'arco (s,w)?Oppure è indifferente?Eseguendo l'algoritmo, nessuna istruzione mi impone vincoli, però mi sono reso conto che in base a come considero l'ordine l'albero risultante della BFS, può differire.
Grazie e spero di essere stato chiaro.
Volevo porvi una domanda sulla visita BFS su di un grafo. Quando devo considerare gli archi che incidono su un nodo u,estratto dalla coda, non ho capito se devo considerarli in un ordine specifico oppure posso procedere arbitrariamente?Cerco di spiegarmi con un esempio:
In questo grafo voglio applicare BFS(G,s), ora dalla coda estraggo s poi considero prima l'arco(s,r) oppure l'arco (s,w)?Oppure è indifferente?Eseguendo l'algoritmo, nessuna istruzione mi impone vincoli, però mi sono reso conto che in base a come considero l'ordine l'albero risultante della BFS, può differire.
Grazie e spero di essere stato chiaro.
Risposte
Nessuno è in grado di darmi una risposta?
L'ordine non ha importanza, basta che tu ne scelga uno e non ripassi per qualcosa di già visto. In genere l'ordine dipende dal modo in cui hai memorizzato in memoria il grafo.
"vict85":
In genere l'ordine dipende dal modo in cui hai memorizzato in memoria il grafo.
Grazie era proprio quello che volevo essere confermato.
Ciao.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo