PDA

Visualizza la versione completa : problema algoritmi su grafi


elpibegiulio
15-07-2012, 21:30
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.

Qualcuno di voi ha qualche idea su come devo procedere???
Vi prego illustratemi i passi per la risoluzione dell'esercizio in modo corretto.

Io pensavo ad una visita DFS ma non so come applicarla

alka
16-07-2012, 10:57
Ti gi stato detto qui (http://forum.html.it/forum/showthread.php?s=&threadid=1513556http://forum.html.it/forum/showthread.php?s=&threadid=1513556) e anche qui (http://forum.html.it/forum/showthread.php?s=&threadid=1513555) che questo non il modo di condurre le discussioni sul forum.

Rileggi il Regolamento (http://forum.html.it/forum/showthread.php?s=&threadid=973887) e segui le norme indicate.

Loading