[Algoritmi] Grafo verificare esistenza cammino
Ciao a tutti.
Come al solito vi scrivo perché sono in difficoltà, mi sono inceppato su questo esercizio: "Dato un grafo non diretto G=(V,E) e tre vertici u,v,w $in$ V, scrivere un algoritmo che decide se esiste un cammino in G che parte da u ed arriva a v, passando per w." Ho buttato giù alcuni ragionamenti, ma non sono corretti, in pratica ho provato a vedere tutti i vertici adiacenti a u e cercavo w se c'era andavo avanti e cercavo negli adiacenti di w il nodo v. Ma ovviamente mi è bastato fare il disegno di un grafo tipo questo, per capire che il ragionamento è sbagliato:
1------6-----7-----8------3
|\
| \
2--4
|
|
5
Purtroppo non riesco a trovare l'algoritmo giusto eppure non dovrebbe essere difficile, ma credo che sbaglio il modo di ragionare per cui vado fuori strada. Spero che un vostro suggerimento possa illuminarmi...grazie
Come al solito vi scrivo perché sono in difficoltà, mi sono inceppato su questo esercizio: "Dato un grafo non diretto G=(V,E) e tre vertici u,v,w $in$ V, scrivere un algoritmo che decide se esiste un cammino in G che parte da u ed arriva a v, passando per w." Ho buttato giù alcuni ragionamenti, ma non sono corretti, in pratica ho provato a vedere tutti i vertici adiacenti a u e cercavo w se c'era andavo avanti e cercavo negli adiacenti di w il nodo v. Ma ovviamente mi è bastato fare il disegno di un grafo tipo questo, per capire che il ragionamento è sbagliato:
1------6-----7-----8------3
|\
| \
2--4
|
|
5
Purtroppo non riesco a trovare l'algoritmo giusto eppure non dovrebbe essere difficile, ma credo che sbaglio il modo di ragionare per cui vado fuori strada. Spero che un vostro suggerimento possa illuminarmi...grazie
Risposte
Spezza il problema in due parti: esiste un cammino da u a w? esiste un cammino da w a v? Ogni cammino del tipo che stai cercando può infatti essere scomposto in questi due cammini.
Ok...ma prendiamo il grafo che ho disegnato prima con u=5, w=6, v=3.
Per vedere se esiste un cammino tra 5 e 6, come faccio?Purtroppo torno sempre sul discorso degli adiacenti, ma è errato o non sono in grado di portarlo avanti. Sinceramente qualcosa mi dice che dovrei farlo ricorsivamente, ma non lo so. Io non so proprio approcciare il ragionamento.
Per vedere se esiste un cammino tra 5 e 6, come faccio?Purtroppo torno sempre sul discorso degli adiacenti, ma è errato o non sono in grado di portarlo avanti. Sinceramente qualcosa mi dice che dovrei farlo ricorsivamente, ma non lo so. Io non so proprio approcciare il ragionamento.
Per vedere se esiste un cammino tra u e w, devo controllare se i due nodi appartengono alla stessa componente connessa, giusto?Quindi mi posso avvalere della BFS o della DFS, giusto?
Rileggendo il tuo problema mi sono reso conto che la richiesta è forse quella di avere un percorso che non ritorni su se stesso. È così? Quale dovrebbe essere la risposta nel caso di (u, v, w) = (5,6,3) nel tuo esempio?
Non è richiesto esplicitamente ma dalla traccia credo si possa dedurre che u è diverso da v. La risposta nel caso (u, v, w) = (5,6,3) è si esiste un cammino che parte da 5 arriva a 3 passando per 6.
Ma non ti sta chiedendo un cammino da 5 a 3 passando da 6, ma da 5 a 6 passando da 3.. Almeno è così se ho capito bene il significato di u, v e w.
Scusami ti ho risposto frettolosamente ed ero convinto che 6 era la w.
Sì, ma allora si considera esistente o meno? Si accetta insomma che il percorso "torni indietro" ad un certo punto?
Mah non saprei dirti,secondo me non bisogna considerare questo caso. Purtroppo questa è la traccia e non ci sono ne esempi ne ulteriori chiarimenti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo