Pages: [1]   Go Down
Print
Author Topic: problema implementazione DFS  (Read 712 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
rox
Forumista
***
Offline Offline

Posts: 633


« on: 05-06-2009, 17:48:28 »

ho provato a implementare il DFS da 0 ma non capisco perchè non funziona.Posto di seguito il codice.
Code:
public class DFS
{
private enum Stato {INESPLORATO, APERTO, CHIUSO}
private Graph g;
private Stato[] st; //ARRAY CONTENENTE GLI STATI DEI NODI VISITATI  ( ci serve per tenere traccia dei nodi che stiamo visitando )
private NodeGraph [] prev; //ARRAY CONTENENTE I GENITORI DEI NODI VISITATI


public DFS (Graph _g)
{
g =_g;
st = new Stato[g.countNode()]; //DIMENSIONO L'ARRAY DEGLI STATI CON LA LUNGHEZZA DELLA LISTA DEI NODI
prev = new NodeGraph[g.countNode()]; //DIMENSIONO L'ARRAY DEI GENITORI CON LA LUNGHEZZA DELLA LISTA DEI NODI
}

public void visita(NodeGraph n) throws Exception
{
NodeGraph A=g.searchNode(n.getInfo());

//INIZIALIZZAZIONE ARRAY
for (int i=0; i<g.countNode(); i++)
{
prev[i] = null; //INIZIALIZZO L'ARRAY A "NULL"
st[i] = Stato.INESPLORATO; //INIZIALIZZO L'ARRAY A "INSESPLORATO"
}
DFSvisit(n);

//INVOCHIAMO PER OGNI NODO DEL GRAFO UNA VISITA
for( int i=0; i<g.countNode(); i++ )
if( st[i] == Stato.INESPLORATO )
DFSvisit( g.getNodeGraph(i) );

//DOPO AVER CONCLUSO LA VISITA, POTRO' STAMPARE A VIDEO L'ARRAY DEI GENITORI
for (int i=0; i<g.countNode(); i++)
if(prev[i] != null)
System.out.println(prev[i].getInfo());
}

public void DFSvisit( NodeGraph n ) throws Exception
{
st[ g.indexNodeGraph(n) ] = Stato.APERTO; //VISITANDO INIZIALMENTE QUESTO NODO LO APRIAMO ( colore = grigio)

Node adiac=n.listaAD.getHead(); //ASSEGNAMO IL PRIMO NODO DELLA LISTA DI ADIACENZA DEL NODOGRAFO "n"

for (; adiac!=null; adiac=adiac.getNext() ) //PER OGNI NODO DELLA LISTA DI ADIACENZA DI "adiac"...
{
int k=g.indexNodeGraph((NodeGraph)adiac.getInfo()); //CONSERVIAMO LA POSIZIONE IN LISTA, DEL NODO DA VISITARE
if( st[k] == Stato.INESPLORATO )//...CONTROLLIAMO SE LO STATO E' "INESPLORATO" ( colore = bianco )
{
prev[k] = n; //ASSEGNIAMO ALL'ARRAY DEI GENITORI "n"
DFSvisit(g.searchNode( ((NodeGraph)adiac.getInfo()).getInfo() ) ); //DOPODICHE' INVOCHIAMO LA VISITA SUL NODO ADIACENTE ("adiac") DI CUI ABBIAMO CONSERVATO
             //NELL'ISTRUZIONE PRIMA IL GENITORE.
}
}

st[g.indexNodeGraph(n)] = Stato.CHIUSO; //USCITI DAL CICLO (" notare le chiamate ricorsive ") A MANO A MANO SI CHIUDONO I VARI NODI ( colore = nero )
}
}

qualcuno mi potrebbe spiegare dove sbaglio?Grazie
Logged

Una macchina è in grado di lavorare come cinquanta uomini comuni, ma nessuna macchina può svolgere il lavoro di un uomo straordinario.
Pages: [1]   Go Up
Print
Jump to: