Newsgroup: it.comp.lang.c
Titolo: Percorsi,cicli e grafi : come gestirli?

Ragazzi vorrei il vostro aiuto per un problema sui grafi.
Ho imparato che un grafo puň essere rappresentato sotto forma di matrice di
adiacenza o come lista di adiacenza.
Mi trovo a risolvere il seguente problema.
"All' interno di una casa ci sono varie stanze individuate con un
numero.Ognuna di queste stanze presenta una o piů aperture che consentono il
passaggio alle altre solo in un verso . Alcune stanze consentono invece il
passaggio alle successive in entrambi i versi.
Si devono trovare i percorsi ,se esistono,che partendo da una stanza
specificata dall' utente fanno ritorno in essa.
Individuare anche i minimi percorsi."
Credo che il precedente sia un problema "tipo" della programmazione come
quello dei collegamenti dei voli aerei.
Io ho pensato di rappresentare il grafo con liste di adiacenza , ma non ho
idea di come continuare : dovrei  visitare ogni collegamento  e poi stampare
a video i percorsi.
Mi sono chiesto :
        Come faccio a tenere memoria dei collegamenti non ancora visitati
presenti nelle liste?
        E come faccio a tenere memoria del percorso?
Vi ringrazio antipatamente del vostro aiuto .

         E come faccio a tenere memoria del percorso?
Potresti rappresentare ogni vertice con una struttura contente le
informazioni che ti servono, in particolare dei flag per quanto riguarda la
visita del veritce e i campi che memorizzano il vertice o i vertici
predecessori nel cammino dalla sorgente al veritce che stai esaminando.
Per trovare il ciclo minimo potresti applicare una visita in ampiezza
(algoritmo BFS) sul grafo. Poi trovare tutti i vertici che hanno il vertice
sorgente adiacente, e risalire attraverso l'albero dei predecesssori fino a
che non trovi appunto il veritce sorgente se non lo trovi vuol dire che non
c'è un ciclo.
Per trovare invece tutti i cammini ciclici non saprei proprio. Forse bisogna
modificare l'agoritmo di visita in modo che dia non solo il predecessore per
il cammino minimo ma anche il predecessore per un cammino qualunque, e poi
lavorare su essi.
Auguri!
P.S
ma che centra con il linguaggio C?

         E come faccio a tenere memoria del percorso?
Potresti rappresentare ogni vertice con una struttura contente le


 ha scritto nel messaggio
news:9hpldk$eti$1...@fe2.cs.interbusiness.it...


Mi trovo a risolvere il seguente problema.
...
Una soluzione possibile e' questa. Definisci una lista (o vettore
o quello che ti pare) di stanze "attive" e inizialmente ci metti
solo la stanza di partenza.
Ad ogni passo prendi le stanze della lista e per ciascuna
  1) contrassegni la stanza come "raggiunta al passo N"
  2) togli la stanza dalla lista delle "attive" e consideri
     tutte le stanze da questa raggiungibili. Per ciascuna
     di queste si possono verificare due casi:
    3a) Hai raggiunto la stanza di partenza (e hai trovato un
        ciclo ed e' lungo N).
    3b) Hai raggiunto questa stanza in precedenza ma non si
        tratta della stanza iniziale (hai trovato un ciclo che
        pero' non  contiene la stanza iniziale). Scarti la
        stanza (sarebbe senza senso girare all'infinito).
    3c) Hai raggiunto una stanza in cui non eri ancora entrato
        e in questo caso aggiungi la stanza alla lista di quelle
        che saranno le stanza attive al prossimo giro
Alla fine della lista delle attive N e ripeti da capo usando
come lista delle "attive" quella in cui hai infilato le stanze
trovate in 3c. Se questa lista e' vuota hai finito di analizzare.
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

     di queste si possono verificare due casi:
Hehehe... ovviamente intendevo 3 casi :D ... i due casi sono
quando cerchi i cicli in genere :)
