Voldx (Normal User)
Newbie
Messaggi: 5
Iscritto: 28/08/2017
|
Ciao a tutti, scrivo in questo forum per sapere come implementare la BFS in java.
Vi spiego qual'è il mio problema. L'algoritmo della visita in ampiezza è perfetta ( nel mio caso) per trovare un percorso minimo.
Il problema è che su internet i vari pseudocodici del BFS sono sopratutto per vedere se un elemento appartiene al grafo,
ma non è il codice che cerco. Ora vi chiedo, esiste un modo affinchè mi ritorna una lista che indica il percorso minimo senza utilizzare l'albero?
Grazie a tutti
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
|
|
Voldx (Normal User)
Newbie
Messaggi: 5
Iscritto: 28/08/2017
|
Affinchè mi torni una lista di nodi che mi indica il percorso senza implentare la struttura dell'albero
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Non riesco a capire cosa centra l'albero... con BFS si parla di grafi.
BFS non e' un algoritmo per trovare il percorso minimo. Ad esempio, se c'e' un ciclo all'interno del grafo, l'algoritmo non trovera' necessariamente il percorso minimo (trovera' UN percorso).
Probabilmente quello che ti serve e' l'algoritmo di Dijkstra le cui implementazioni in Java sono disponibili a migliaia (fai una ricerca su Google/GitHub): https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
|
|
lumo (Member)
Expert
Messaggi: 449
Iscritto: 18/04/2010
|
Per ogni nodo salva il nodo precedente nella visita BFS, e poi ripercorri al contrario.
BFS non e' un algoritmo per trovare il percorso minimo. Ad esempio, se c'e' un ciclo all'interno del grafo, l'algoritmo non trovera' necessariamente il percorso minimo (trovera' UN percorso). |
Se si parla di grafi con archi non pesati, allora BFS trova il percorso minimo, e la presenza di cicli non dovrebbe cambiare nulla no? |
|
Roby94 (Member)
Guru
Messaggi: 1170
Iscritto: 28/12/2009
|
Postato originariamente da lumo:
Se si parla di grafi con archi non pesati, allora BFS trova il percorso minimo, e la presenza di cicli non dovrebbe cambiare nulla no? |
Credo che Piero intenda che l'algoritmo BFS come è concepito ti dice solo se un nodo è presente o no in un grafico; ovviamente nulla vieta di modificarlo come proponi tu per cambiarne totalmente la funzione, ma a questo punto non si puo parlare piu di BFS. |
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Postato originariamente da Roby94:
ma a questo punto non si puo parlare piu di BFS. |
|
|
pierotofy (Admin)
Guru^2
Messaggi: 6230
Iscritto: 04/12/2003
|
Postato originariamente da lumo:
Se si parla di grafi con archi non pesati, allora BFS trova il percorso minimo, e la presenza di cicli non dovrebbe cambiare nulla no?
|
Si hai regione, avevo confuso con DFS. Ignorate il mio commento di prima. Ultima modifica effettuata da pierotofy il 13/12/2017 alle 20:10
|
|
Voldx (Normal User)
Newbie
Messaggi: 5
Iscritto: 28/08/2017
|
Infatti a me il percorso non è pesato...cmq grazie a tutti
|
|