[C] Implementazione algoritmo Depth First Search

[darksergio]

Salve, ho implementato un codice per costruire una matrice di adiacenze di un grafo non orientato rappresentante un labirinto che intendevo visitare con l'algoritmo DFS... a questo punto ho fatto delle ricerche su quest' algoritmo ma sono riuscito a trovare solo funzione ricorsive su liste multiple mentre io volevo implementarlo iterativamente sulla matrice...
avrei bisogno di una spiegazione su come visitare i vari nodi a partire dalla matrice e di come implementare l'algoritmo in maniera iterativa...

il codice per formare la matrice è questo

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

/*Scrivere function C per la visita di un grafo mediante l’algoritmo Depth First Search iterativo.
Applicare l’algoritmo al grafo che descrive il seguente labirinto per determinare un cammino
che parte dall’ingresso A e termina nell’uscita Q. */

typedef struct
{
 char a;
 char v;
}elem;

elem** trimatrix(int);
void   visualmat(int,elem**);

int main ()
{
   elem **m;
   m=trimatrix(27);
   (m[1][0]).a=1;(m[2][1]).a=1;(m[3][0]).a=1;(m[3][1]).a=1;(m[4][3]).a=1;
   (m[5][4]).a=1;(m[6][5]).a=1;(m[7][6]).a=1;(m[8][5]).a=1;(m[10][9]).a=1;
   (m[11][7]).a=1;(m[12][8]).a=1;(m[12][11]).a=1;(m[13][11]).a=1;(m[14][13]).a=1;
   (m[15][12]).a=1;(m[15][14]).a=1;(m[16][14]).a=1;(m[17][13]).a=1;(m[18][16]).a=1;
   (m[18][17]).a=1;(m[19][17]).a=1;(m[20][16]).a=1;(m[21][20]).a=1;(m[21][19]).a=1;
   (m[22][21]).a=1;(m[24][9]).a=1;(m[24][22]).a=1;(m[24][23]).a=1;(m[25][7]).a=1;
   (m[25][20]).a=1;(m[25][23]).a=1;(m[26][0]).a=1;(m[26][1]).a=1;(m[26][10]).a=1;
   visualmat(27,m);

   return 0;
}


elem**  trimatrix(int n)
{
 /*Crea una matrice dinamica frastagliata in modo
   da risparmiare memoria allocando solo  il triangolo
   inferiore della matrice di adiacenze in virtù delle
   proprietà di simmetria dei grafi non orientati*/

   elem **matrice;
   int i;

   /*alloca un array di puntatori*/
   matrice=(elem**)calloc(n,sizeof(elem*));
   if(matrice==NULL)
   {printf("memoria insufficente!");exit(1);}

  /*inserisce i puntatori all'interno dell'array*/
   for(i=0;i<n;i++)
   {
     matrice[i]=(elem*)calloc(i+1,sizeof(elem));
     if(matrice==NULL)
     {printf("memoria insufficente!");exit(2);}
   }

   return matrice;
}

void   visualmat(int n,elem **m)
{
 /*visualizzazione classica del
   triangolo inferiore di una matrice*/

   int i,j;

   printf("\n\n--Matrice di Adiacenze--\n\n");

   for(i=0;i<n;i++)
   {
    printf("%c ",i+97);
     for(j=0;j<i+1;j++)
      printf("%d",(m[i][j]).a);
    printf("\n");
   }
}

sareste così gentili da darmi una mano?

Grazie e cordiali saluti

[ramy89]

Per farlo in maniera iterativa ti serve una pila.
Nel tuo caso è facile perchè ci sono solo interi da memorizzare.
L' algoritmo è questo:
1)Metti il nodo dal quale vuoi fare partire la visita in pila;
2)Finchè la pila non è vuota:
-Estrai un nodo dalla pila (è un intero);
-Visiti quel nodo;
-Metti in pila tutti i nodi adiacenti a quel nodo che non sono ancora stati visitati.

Per tenere traccia dei nodi già visitati in genere si usa un vettore di booleani, ma puoi usare qualsiasi struttura.
A questo punto siccome sai già qual' è il numero di nodi, la pila puoi implementarla semplicemente tramite un vettore, tenendo traccia dell' ultimo indice "valido" della pila.

[darksergio]

il problema è: io praticamente faccio corrispondere il nodo all'indice di riga dell'array, ovvero: 0=a, 1=b, 2=c etc...

come faccio a "visitare" il nodo, e come gestisco la pila??? voglio dire, visto che non si tratta di liste multiple in cui ho fisicamente dei nodi da gestire, come posso regolarmi?

[ramy89]

Per la pila no, ogni indice dell' array è un indice che devi leggere per capire quale elemento della pila, cioè quale nodo, contiene.
Ad esempio [3,1,2] contiene i nodi 3,1,2 in maniera indipendente dall' indice, in questo caso i nodi li aggiungi in fondo all' array, tieni traccia dell' ultimo indice valido che in questo caso è 2.Per estrarlo semplicemente decrementi l' ultimo indice valido.
L' array in questo caso avrà n elementi allocati.
Per quanto riguarda la visita, la matrice di adiacenza per definizione contiene nell' indice i,j 1 se i è adiacente a j, 0 altrimenti.
Non confondere i nodi con gli elementi della matrice, per memorizzare i nodi ti basta un vettore di n elementi di tipo elem.
Per vedere se il nodo i è adiacente al nodo j (indice del vettore di n nodi di tipo elem), leggi la matrice di adiacenza, che deve essere di interi, non di elem.
Se vuoi visitare il nodo i leggi nel vettore di elem l' elemento di indice i, per trovare i suoi nodi adiacenti leggi tutta la riga o la colonna (visto che il grafo è non orientato, la matrice è simmetrica) i-esima.

[darksergio]

per array intendevo l'array bidimensionale ovvero la matrice mi sono espresso male io... ti chiedo scusa...

per il resto... accidenti è un casino... io l'avevo fatta di elem per la questione del flag, ma hai ragione... confondevo i nodi con gli elementi della matrice... quindi come devo fare per la questione del flag a nodo che mi dice se il nodo è già stato visitato...? diamine credevo fosse + semplice

[darksergio]

per facilitarci la comunicazione-> parliamo di matrice in caso di matrice di adiacenze e di vettore in caso di pila

[ramy89]

In realtà è più scemplice ora, perchè per trovare un nodo ti basta scorrere il vettore dei nodi (di tipo elem).
Ti faccio un esempio di come puoi gestire la cosa, giusto come input di avvio:

#define N 27
int main ()
{
    elem *nodi;   
    int **mat;                                    // L' allocazione ti consiglio di farla nel main
    nodi=(elem*)malloc(N*sizeof(elem));
    mat=(int**)malloc(N*sizeof(int*));
    for(int i=0;i<N;i++)
        mat[i]=(int*)calloc(N,sizeof(int));
    // per creare un arco da i a j inizializzi mat[i][j] e mat[j][i] a 1
    // inizializzi il vettore dei nodi
    return 0;
}

Ora hai la matrice che ti dice le adiacenze (gli archi) tra i nodi.
Per trovare la lista di adiacenza del nodo i-esimo:

for(int j=0;j<N;j++)
{
    if(mat[i][j]==1)  // un nodo non dovrebbe mai essere adiacente a se stesso
    {                       // per cui se hai inizializzato bene la matrice, non si entra
                            // nell' if se i è uguale a j
        // nodi[j] è il nodo adiacente al nodo nodi[i]
    }
}

Siccome la matrice è simmetrica puoi scegliere se scorrere una riga o una colonna.
Inizia dalle cose semplici, nella dfs ora prova a trovare la lista di adiacenza di un nodo.

[darksergio]

intendi così??

void visitadfs(char val,elem *nod,char **matrice)
{
   int i=val-97,j;

  printf("\nnodi adiacenti ad [%c]: ",nod[i].info);
   for(j=0;j<size;j++)
     if(matrice[j][i]==1)
       printf("%c ",nod[j].info);
}

[darksergio]

sono riuscito ad arrivare a questo codice, tuttavia c'è qualcosa che non va a livello logico poiché durante la scansione l'ipotetico viaggiatore interno al labirinto (è per questo che mi serviva l'algoritmo) rimane imbottigliato per essere precisi dopo aver percorso

a->{->k->j->y->x->d->b->c->e->f->i->m->l->h si trova in posizione c dove tutti gli altri nodi adiacenti sono già stati visitati...

di seguito riporto il codice:

Funzione che visita il nodo corrente e dispone gli elementi in stack:

void visitnodo(char val,elem *nod,char **matrice,elem *stack,int *head)
{
   int i=val-97,j;

   nod[i].flag=1;

   /*conta archi di colonna evitando l'arco cappio
    che altrimenti verrebbe contato 2 volte
    e li inserisce nello stack*/
   for(j=i+1;j<size;j++)
     if(matrice[j][i]==1);
       push(stack,nod[j],head)

  /*conta archi di riga considerando l'arco cappio
    e li inserisce nello stack*/
   for(j=0;j<i+1;j++)
     if(matrice[i][j]==1)
       push(stack,nod[j],head);

      //for(j=0; j<*head+1; j++)//stampa a schermo lo stack
      //printf("\nstack[%d] %c-%d",j,stack[j].info,stack[j].flag);
}

Funzione DFS:

void visitadfs(elem *nodi,char **matrice,elem *stack,int *head)
{
   elem c;

   printf(" -%c- ",nodi[0].info);

   visitnodo(nodi[0].info,nodi,matrice,stack,head);

   while(head!=NULL)
   {
    c=stack[*head];
    pop(stack,head);
    if(c.flag==0 && c.info!='q')
     {
      printf(" -%c- ",c.info);
      visitnodo(c.info,nodi,matrice,stack,head);
     }
   }
}

Grafo - Labirinto:

[darksergio]

Nada?