Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Java - BFS in java
Forum - Java - BFS in java

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
Voldx (Normal User)
Newbie


Messaggi: 5
Iscritto: 28/08/2017

Segnala al moderatore
Postato alle 16:35
Martedì, 12/12/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:asd:

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 4:41
Mercoledì, 13/12/2017
https://github.com/techpanja/interviewproblems/blob/master/ ...

Non sono sicuro di capire cosa intendi per "ritorna una lista che indica il percorso minimo senza utilizzare l'albero".


Il mio blog: https://piero.dev
PM Quote
Avatar
Voldx (Normal User)
Newbie


Messaggi: 5
Iscritto: 28/08/2017

Segnala al moderatore
Postato alle 11:57
Mercoledì, 13/12/2017
Affinchè mi torni una lista di nodi che mi indica il percorso senza implentare la struttura dell'albero

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 14:52
Mercoledì, 13/12/2017
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


Il mio blog: https://piero.dev
PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 449
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 17:29
Mercoledì, 13/12/2017
Per ogni nodo salva il nodo precedente nella visita BFS, e poi ripercorri al contrario.

Testo quotato

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?

PM Quote
Avatar
Roby94 (Member)
Guru


Messaggi: 1170
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 18:10
Mercoledì, 13/12/2017
Testo quotato

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.

PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 20:04
Mercoledì, 13/12/2017
Testo quotato

Postato originariamente da Roby94:
ma a questo punto non si puo parlare piu di BFS.



:k:


Il mio blog: https://piero.dev
PM Quote
Avatar
pierotofy (Admin)
Guru^2


Messaggi: 6230
Iscritto: 04/12/2003

Segnala al moderatore
Postato alle 20:09
Mercoledì, 13/12/2017
Testo quotato


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


Il mio blog: https://piero.dev
PM Quote
Avatar
Voldx (Normal User)
Newbie


Messaggi: 5
Iscritto: 28/08/2017

Segnala al moderatore
Postato alle 20:24
Mercoledì, 13/12/2017
Infatti a me il percorso non è pesato...cmq grazie a tutti :)

PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo