[C] Grafi: ritorna tutti i cammini semplici

[-hide-]

Un compito d'esame presenta questo quesito:

Si scriva una funzione, in linguaggio C, che preso in ingresso un grafo G=(V,E) e due vertici a, b appartenenti a V, ritorni l'insieme di tutti i cammini semplici da a -> b. Si utilizzi, per realizzare l'algoritmo, la tecnica del backtracking.

NOTA: Un cammino si dice semplice se composto da nodi distinti.

Ho immediatamente pensato di iniziare da un altro esercizio, già da me svolto, in cui bisogna far tornare il primo cammino semplice che si viene ad incontrare. Posto qui di seguito il codice:

void pathsearch (struct graph *ADJ[], int DIM, int a, int b, struct lista *L, int *visited[], int *trovato) {
   struct graph *temp;
   visited[a] = 1;
   insTail (L,a);
   if (a==b) {
      *trovato = 1;
      return;
   }
   for (temp=ADJ[a]; temp!=NULL; temp=temp->next)
      if (!visited[temp->v])
         pathsearch (ADJ, V, a, b, L, visited, trovato);
   if (!(*trovato)) {
      delTail (L);
      visited[a] = 0;
   }
}

Se non capite o volete che implementi anche le strutture dati dite pure.
Avevo pensato bastasse aggiungere un IF dopo l'ultimo che, alternativamente ad esso, non eliminasse l'elemento dalla coda ma non mi convince.
Suggerimenti?!

[tuccio`]

   if (!(*trovato)) {
      delTail (L);
      visited[a] = 0;
   }

eliminarlo dalla coda è corretto, ma, mettendo visited[a] a 0, rischi di andare a visitare di nuovo il nodo se ci ripassi, rifacendo il ciclo che ovviamente sarà infruttuoso, credo sia meglio lasciarlo a 1

comunque anche così dovrebbe terminare l'algoritmo

per il resto, mi sembra corretto, cos'ha che non va?

[-hide-]

Originariamente inviato da tuccio`

   if (!(*trovato)) {
      delTail (L);
      visited[a] = 0;
   }

eliminarlo dalla coda è corretto, ma, mettendo visited[a] a 0, rischi di andare a visitare di nuovo il nodo se ci ripassi, rifacendo il ciclo che ovviamente sarà infruttuoso, credo sia meglio lasciarlo a 1

L'ho inserito perché proprio quel flag impostato ad 1 non mi permetteva di tornare su un nodo, che era per l'appunto il b. Ho provato questo codice su un nodo connesso non orientato da me inventato. Posso dare un'altra occhiata ma se non ricordo male è proprio quell'aggiunta che mi permetteva di chiudere correttamente il programma.

Originariamente inviato da tuccio`

comunque anche così dovrebbe terminare l'algoritmo
per il resto, mi sembra corretto, cos'ha che non va?

Ma questo non è il modo per ottenere uno ed un solo cammino a -> b?! Io li vorrei avere tutti, quindi il codice mi deve permettere di tornare indietro e controllare se ci sono altre vie. Con questo codice, appena arrivo a b chiude!

[tuccio`]

non è vero che arrivi a b e chiude

se avessi

return pathsearch (ADJ, V, a, b, L, visited, trovato);

al posto delle tue chiamate ricorsive chiuderebbe tutte le chiamate precedenti quando arrivi a b

invece una volta fatto il primo return torna all'ultimo vertice (chiamiamolo v) che ti ha condotto effettivamente a b e continua a ciclare in cerca di un altro cammino che ti conduce a b

ps: sulla storia di togliere il flag hai ragione tu

[-hide-]

Originariamente inviato da tuccio`

non è vero che arrivi a b e chiude

se avessi

return pathsearch (ADJ, V, a, b, L, visited, trovato);

al posto delle tue chiamate ricorsive chiuderebbe tutte le chiamate precedenti quando arrivi a b

invece una volta fatto il primo return torna all'ultimo vertice (chiamiamolo v) che ti ha condotto effettivamente a b e continua a ciclare in cerca di un altro cammino che ti conduce a b

ps: sulla storia di togliere il flag hai ragione tu

Ho da poco provato il codice e devo ammettere che non mi è risultato corretto né nella ricerca di un solo cammino ne nella ricerca di più cammini, sia con che senza il return che tu mi hai consigliato di aggiungere.
Ora non posso ma credo che nella giornata di domani scannerizzo il mio lavoro e te lo faccio vedere per conferma perché parlare così diventa molto difficile

[tuccio`]

sì in realtà dovresti ritornare solo se *trovato == 1 per fare quella cosa che dici (cioè ritornare appena lo trovi), sennò continui a visitare il grafo

[-hide-]

Ho appena terminato di lavorare sul codice inerente la ricerca di un solo cammino. Credo di aver trovato l'aggiunta vincente; la trovi in grassetto nel codice stesso.

void pathsearch (struct graph *ADJ[], int DIM, int a, int b, struct lista *L, int *visited[], int *trovato) {
   struct graph *temp;
   visited[a] = 1;
   insTail (L,a);
   if (a==b) {
      *trovato = 1;
      return;
   }
   for (temp=ADJ[a]; temp!=NULL && !(*trovato); temp=temp->next)
      if (!visited[temp->v])
         pathsearch (ADJ, V, a, b, L, visited, trovato);
   if (!(*trovato)) {
      delTail (L);
      visited[a] = 0;
   }
}

Inoltre, per conferma, ho provveduto ad eseguire il codice su un foglio.

Provo a risolvere il problema dei più percorsi.