Visualizzazione dei risultati da 1 a 9 su 9
  1. #1

    trovare cicli in un grafo

    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

  2. #2

  3. #3
    Utente di HTML.it L'avatar di newbie
    Registrato dal
    Dec 2005
    Messaggi
    299
    Si potrebbe usare un algoritmo ricorsivo di esplorazione in profondità, del tipo:
    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!
    Fa un tantino schifo, ma dovrebbe funzionare...

    Svegliati, Neo. Matrix ti possiede...

  4. #4
    Utente di HTML.it L'avatar di byaur
    Registrato dal
    Aug 2004
    Messaggi
    1,061
    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

  5. #5
    Utente di HTML.it L'avatar di newbie
    Registrato dal
    Dec 2005
    Messaggi
    299
    Effettivamente...
    codice:
    b - g
    |   | \
    a - c - f
    | 
    d - e
    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?
    Svegliati, Neo. Matrix ti possiede...

  6. #6
    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

  7. #7
    Utente di HTML.it L'avatar di newbie
    Registrato dal
    Dec 2005
    Messaggi
    299
    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
    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.
    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...

  8. #8
    Si, una dfs sola basta per visitare tutti i nodi del grafo, ma non per trovare tutti i cicli... ahimè...

  9. #9
    Utente di HTML.it L'avatar di newbie
    Registrato dal
    Dec 2005
    Messaggi
    299
    Originariamente inviato da ChiaraMorgana
    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?
    Succederebbe una cosa del genere solo nei grafi orientati...
    Svegliati, Neo. Matrix ti possiede...

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.