Dato un grafo non direzionato, qual'è il modo migliore per trovare tutti i cicli?
Esiste qualche algoritmo già fatto? Ho un po' cercato ma non ne ho trovati...
Chiara
Dato un grafo non direzionato, qual'è il modo migliore per trovare tutti i cicli?
Esiste qualche algoritmo già fatto? Ho un po' cercato ma non ne ho trovati...
Chiara
Si potrebbe usare un algoritmo ricorsivo di esplorazione in profondità, del tipo:
Fa un tantino schifo, ma dovrebbe funzionare...codice:Nodo nodoIniziale; //globale void esplora(nodo) { if(nodo == nodoIniziale) hai trovato un ciclo else { if(nodo ha adiacenti) esplora(ogni adiacente) //ricorsione else è una foglia, ramo morto } } nodoIniziale = N; esplora(nodoIniziale); Ad esempio, dato un grafo b - g | a - c - f | / d - e avresti nodoIniziale = a esplora(a), ha adiacenti --esplora(b), ha adiacenti ----esplora(g), ramo morto --esplora(c), ha adiacenti ----esplora(f), ramo morto ----esplora(d), ha adiacenti ------esplora(e), ramo morto ------esplora(a), == nodoIniziale => CICLO!
Svegliati, Neo. Matrix ti possiede...
difficilmente funziona!!!
basta un controesempio...
prova, con il grafo di prima a modificarlo cosi,togliendo il vecchio ciclo e inserendo un ciclo tra g-c-f
(scusate, ma si vede male)
b - g
| | \
a - c - f
|
d - e
partendo da A, scelto come nodo iniziale, il tuo algoritmo non funziona(infatti continua a visitare g-c-f senza che il contronto con il nodo iniziale sia vero e quindi secondo il tuo algoritmo non c'è un ciclo, mentre invece c'è), o peggio può andare in loop se non prevedi un marcamento dei nodi visitati...
Chi di noi non vorrebbe
sollevare il velo sotto cui sta nascosto il
futuro...
David Hilbert
Effettivamente...
E se si creasse una lista dei nodi visitati e si facesse fermare l'algoritmo (dicendo che c'è un ciclo) quando si va ad esplorare un modo già visitato?codice:b - g | | \ a - c - f | d - e
Svegliati, Neo. Matrix ti possiede...
Per fare il giro di tutti i nodi basta usare la dfs,(depth first search) che tiene conto dei nodi gia' visitati... pero' non trova tutti i cicli... bisognerebbe farla tante volte quanti sono i nodi... un sacco di tempo!
Chiara
In realtà, se il grafo è connesso (cioè se da qualsiasi nodo se ne può raggiungere un altro), basta una sola DFS per visitarlo tutto. Se, al limite, non lo è, sarà diviso in tanti grafini più piccoli separati tra loro: in questo caso, basta scegliere un nodo per ognuno e fare una DFS per ogni nodo scelto. In termini più semplici, se il grafo ha N è diviso in P pezzi (magari uno), bastano P visite.Originariamente inviato da ChiaraMorgana
Per fare il giro di tutti i nodi basta usare la dfs,(depth first search) che tiene conto dei nodi gia' visitati... pero' non trova tutti i cicli... bisognerebbe farla tante volte quanti sono i nodi... un sacco di tempo!
Chiara
Per sapere se un pezzo è stato visitato o meno, basta creare una lista NNV dei nodi non ancora visitati. Dopo averla riempita con tutti i nodi, basta far partire la DFS dal primo, eliminando da NNV tutti i nodi toccati: in questo modo in NNV restano solo i nodi degli altri pezzi. Scelto un altro nodo, si visiterà il pezzo successivo... e così via.
Almeno credo...
Svegliati, Neo. Matrix ti possiede...
Si, una dfs sola basta per visitare tutti i nodi del grafo, ma non per trovare tutti i cicli... ahimè...
Ma proprio perchè visiti tutti i nodi dovresti rilevare tutti i cicli... perchè continuo a non capire dove dov'è l'inghippo?Originariamente inviato da ChiaraMorgana
Si, una dfs sola basta per visitare tutti i nodi del grafo, ma non per trovare tutti i cicli... ahimè...
Succederebbe una cosa del genere solo nei grafi orientati...
Svegliati, Neo. Matrix ti possiede...