[C] Stampare le componenti fortemente connesse di un grafo orientato

[totoscibetta]

Salve ragazzi, devo sostenere un esame di programmazione in c e non riesco a tradurre lo pseudocodice dell'algoritmo che stampa le componenti fortemente connesse di un grafo orientato. Vi allego la struttura del mio grafo e chiedo un aiuto per riuscire ad implementare questo algoritmo. Grazie mille

/* Grafo_orientato */
     #include <stdio.h>
     #include <stdlib.h>
     
     struct arco {
          int data;
          struct arco *lista_ad; 
     };
     typedef struct arco A;

     struct vertice {
          int data;
          struct vertice *v_successivo;
          A *lista_ad;
       };
     typedef struct vertice V;

     V* aggiungi_v(V *origine, int d) {
          V *n = (V*)malloc(sizeof(V)); n->data = d;
          n->lista_ad = NULL;
          n->v_successivo = origine;
          return n; 
     }

     V* cerca_v(V *origine, int d) {
          if( origine == NULL ) 
               return NULL;
          if( origine->data == d ) 
               return origine;
          return cerca_v(origine->v_successivo, d);
     }

     V* aggiungi_a(V *origine, int a, int b) {
          V *u;
          u = cerca_v(origine, a);
          A *v = (A*)malloc(sizeof(A)); 
          v->data = b;
          v->lista_ad = u->lista_ad;
          u->lista_ad = v;
          return origine;
     }

     void stampa_v_rec(V *origine) {
          if( origine == NULL ) 
               return;
          printf("%d -> ", origine->data);
          stampa_v_rec(origine->v_successivo); 
    }

     void stampa_v(V *origine) {
          if( origine == NULL ) {
               printf("Non ci sono vertici!\n");
               return; 
          }
          printf("I vertici  nel grafo sono:\n");
          stampa_v_rec(origine);
          printf("FINE.\n");
     }

     void stampa_a_rec(V *origine) {
         if( origine == NULL ) 
               return;
         A *u;
         u = origine->lista_ad;
         
         while(u!=NULL){
                  printf("( %d, %d)\n", origine->data, u->data );
                 u = u->lista_ad;
         }

         stampa_a_rec(origine->v_successivo); }
         void stampa_a(V *origine) {
                  if( origine == NULL ) {
                      printf("Non ci sono archi!\n");
                       return; 
                   }
         printf("Gli archi presenti nel grafo sono:\n"); 
         stampa_a_rec(origine);
    }

     main() {
          V *origine = (V*)malloc(sizeof(V)); 
          origine = NULL;
          origine = aggiungi_v(origine, 1); 
          origine = aggiungi_v(origine, 2);
          origine = aggiungi_v(origine, 3); 
          origine = aggiungi_v(origine, 4); 
          origine = aggiungi_v(origine, 5); 
          origine = aggiungi_v(origine, 6); 
          origine = aggiungi_v(origine, 7); 
          origine = aggiungi_v(origine, 8); 
          origine = aggiungi_v(origine, 9); 
          origine = aggiungi_v(origine, 10);
         aggiungi_a(origine, 1, 5);
         aggiungi_a(origine, 2, 4);
         aggiungi_a(origine, 1, 3);
         aggiungi_a(origine, 4, 3);
         aggiungi_a(origine, 4, 5);
         aggiungi_a(origine, 5, 2);
         aggiungi_a(origine, 1, 6);
         aggiungi_a(origine, 6, 7);
         aggiungi_a(origine, 9, 6);
         aggiungi_a(origine, 7, 1);
         aggiungi_a(origine, 7, 2);
         aggiungi_a(origine, 5, 7);
         aggiungi_a(origine, 8, 3);
         aggiungi_a(origine, 4, 8);
         aggiungi_a(origine, 4, 9);
         aggiungi_a(origine, 5, 9);
         aggiungi_a(origine, 10, 9);
         aggiungi_a(origine, 10, 4);
         aggiungi_a(origine, 10, 3);

         stampa_v(origine);
         stampa_a(origine);
}

[Who am I]

Che algoritmo stai utilizzando? Posso vedere lo pseudocodice?

[totoscibetta]

Ecco lo pseudocodice:

procedura visitaFortementeConnesse(){
    numeroDFS=contatore
    contatore++
    fuga(v)=numeroDFS(v)
    for each (arco(v,w) in G)do
        if(u non ancora in T) then
            aggiungi (v, w) a T
            P.push(w)
            visitaFortementeConnesse(w, P)
            fuga(v)= min{fuga(v), fuga(w)}
        else
            fuga(v)=min{fuga(v), numeroDFS(w)}
    if(fuga(v) = numeroDFS(v)) then
        do                                            {stampa tutti i vertici della componente [v]}
            u=p.pop()
            stampa il vertice u
            elimina u e tutti gli archi incidenti su u
        while(u!=v)
}

algoritmo fortementeConnesse( grafo G){
    contatore =1;
    Pila p;
    crea un nuovo vertice x con archi (x,v) per tutti i vertici v
    T<-- albero contenente un solo vertice x
    visitaFortementeConnesse(x,p)
}

Elenco alcune definizioni:

numeroDFS(v) è il numero di vertici visitati prima di v
fuga(v) è il vertice con il più piccolo numeroDFS raggiungibile con un arco uscente dal sottoalbero di radice v

Non è detto che da un vertice è possibile raggiungere tutti gli altri vertici del grafo, quindi si deve aggiungere un nuovo vertice connesso a tutti gli altri vertici.

Si deve fare una visita DFS del grafo per trovare la testa di una componente fortemente connessa, quindi v è la testa se numeroDFS(v)=fuga(v). Il contatore può essere implementato tramite una variabile static, in modo tale da conservare il valore per il giusto assegnamento del numero DFS; La pila mi sembra superflua, a voi la parola....