Trovare cicli

[f0/\/2!3]

Salve,
ho un problema che ha a che fare con un grafo direzionato.

Dovrei trovare tutti i cicli al suo interno e per ogni ciclo eventualmente identificarlo univocamente così da permettermi di svolgere dei calcoli basandomi sulle label degli archi che compongono il ciclo.

Ho sentito che può essere un problema facilmente esponenziale e ciò non posso permettermelo...

(Il tutto andrà implementato in java...)

COME FARE???

[Angus]

Salve,
ho un problema che ha a che fare con un grafo direzionato.

Dovrei trovare tutti i cicli al suo interno e per ogni ciclo eventualmente identificarlo univocamente così da permettermi di svolgere dei calcoli basandomi sulle label degli archi che compongono il ciclo.

Ho sentito che può essere un problema facilmente esponenziale e ciò non posso permettermelo...

(Il tutto andrà implementato in java...)

COME FARE???

Se per ciclo intendi un ciclo semplice, cioè dove solo i vertici iniziale e finale sono uguali, allora un'idea è utilizzare un algoritmo DFS (http://en.wikipedia.org/wiki/Depth-first_search) , durante il quale puoi accorgerti se stai visitando un nodo già visitato in precedenza, e marcare il cammino effettuato come ciclo. Questo tipo di algoritmo dovrebbe essere lineare, O(|V| + |A|).