Percorsi semplici in un grafo

[Check19]

Ciao ragazzi, spero qualcuno possa darmi una mano con questo esercizio:

Dato un grafo orientato G rappresentato con liste di adiacenza, si scriva in pseudo-codice, un algoritmo che, dati in ingresso G e tre vertici s,v e u , stampi tutti i percorsi semplici che portano da s a v passando per il vertice u

Penso si risolva con una BFS o un DFS ma non so come.

[banryu79]

Cosa si intende per "percorsi semplici"?

Comunque, l'osservazione banale è che il problema è riducibile al calcolare tutti i "percorsi semplici" tra due vertici nel grafo.
Quindi, avendo questo algoritmo, lo applichi due volte: la prima volta per calcolare tutti i "percorsi semplici" tra s e u, la seconda volta per calcolare tutti i "percorsi semplici" tra u e v.
A questo punto, la soluzione è data dalla combinazione dei percorsi s -> u con quelli u -> v.

[DanieleC88]

Un percorso semplice è una sequenza di nodi/archi in cui non compaiono cicli. Io farei una DFS, marcando (o "colorando") i nodi visitati. Se torno sui miei passi (su un nodo già marcato) sto introducendo un ciclo, per cui posso scartare quel percorso. Se giungo al nodo di destinazione, il percorso che ho delineato fino a quel punto è buono, e lo aggiungerò ad un insieme di percorsi validi.

Il resto lo ho già detto banryu79.

[Check19]

Prima di tutto grazie per le risposte!
Faccio un esempio in modo che sia tutto più chiaro, mettiamo che il grafo in questione sia questo (scrivo le liste di adiacenza di ogni vertice):

adj[s] = A,B
adj[A] = U
adj[b] = U
adj[u] = V

Allora i percorsi semplici che rispondo al quesito della traccia sono

S->A->U->V
S->B->U->V

Anche io avevo pensato ad una DFS, ma nel momento in cui trovo il primo percorso , U risulterà già colorato, quindi non lo andrò ad esaminare e il percorso S->B->U->V non verrà stampato...sbaglio qualcosa nel ragionamento?

[banryu79]

Originariamente inviato da Check19

...percorso S->B->U->V non verrà stampato...sbaglio qualcosa nel ragionamento?

Te l'avevo già scritto

Comunque, l'osservazione banale è che il problema è riducibile al calcolare tutti i "percorsi semplici" tra due vertici nel grafo.
Quindi, avendo questo algoritmo, lo applichi due volte:

Spezza il problema:
- calcola i percorsi semplici da S a U ([SAU] e [SBU])
- calcola i percorsi semplici da U a V ([UV])
- componi i ogni percoso della prima soluzione con ogni percorso della seconda ([SAU+UV]=[SAUV] e [SBU+UV]=[SBUV])

In pratica devi solo scrive un algoritmo che trovi tutti i percorsi semplici tra due vertici di un grafo e poi usare la logica qui sopra.

[Check19]

Ok, ho capito il ragionamento. Ora provo a implementare il tutto in pseudocodice!