[ALGORITMO] Trovare un ciclo in un grafo

[elpibegiulio]

Ho bisogno del vostro aiuto visto che non riesco a risolvere il seguente esercizio:
Il testo dice:
Progetta un algoritmo che sia in grado di rimuovere tutti i cicli di un grafo orientato G=(V,E) in tempo O(m+n) ,dove m è il numero di archi ed n è il numero di vertici del grafo. Rimuovere un ciclo significa rimuovere un arco del ciclo . Se ci sono l cicli in G il tuo algoritmo dovrebbe rimuovere solo O(l) archi.

Vi posto la mia soluzione:
pensavo di fare una visita DFS. Appena viene trovato un arco che non appartiene all'albero DFS viene eliminato...così elimino l'arco che non appartiene all'albero e che costituisce un ciclo....penso che sia così ma ho un altro problema... può succedere che così si tolga anche archi che non fanno parte di un ciclo...
come posso risolvere secondo voi???

[nicolabiondo]

Si, la DFS va bene come strategia per verificare se ci sono cicli in un grafo. E ti permette di farlo in O(m+n)

Un grafo orientato e aciclico se durante una visita DFS non si incontrano archi all'indietro cioè, se durante la visita del nodo u non si incontra un arco (u,v) tale che v sia un nodo visitato e
appartenga al cammino corrente che va dal nodo iniziale (radice della visita) al nodo u.

struct structgrafo {
int NODI [ n+1]; // vettore dei nodi 
int ARCHI [ m ]; // vettore degli insiemi di  adiacenza 
boolean VISITATO [ n ]; // vettore dei nodi visitati 
boolean CAMMINO [ n ]; // vettore booleano che descrive il cammino corrente 
boolean aciclico; // variabile booleana 
}; 

typedef struct structgrafo  grafo;

void ACICLICO ( grafo G , nodo u )
{
   int i ;
   nodo v ;
   G -> CAMMINO [u] = TRUE; // u appartiene al cammino corrente
   G-> VISITATO [u] = TRUE; // marca u visitato
   for ( i = G->NODI [u]; i < G->NODI [u+1]; i++ )
   {
      v = G->ARCHI [i]; // nodo adiacente
      if (! G->VISITATO [v])
         ACICLICO (G ,v);
      else
         if (G->CAMMINO [v] == TRUE)
         G->aciclico = FALSE;
   }
   G->CAMMINO [u] = FALSE; // u NON appartiene al cammino corrente
}

[elpibegiulio]

a me interessava solo una spiegazione, comunque visto che è un esercizio tipo esame ,dici che basta scrivere la spiegazione che mi hai dato tu. Come glielo dimostro che impiega tempo O(m+n)?

[nicolabiondo]

sai dimostrare che DFS impiega tempo O(n+m)?

[elpibegiulio]

si è lo stesso tempo di un visita generica o di un visita in ampiezza.