Grafi in java

[sabbia89]

Buonasera a tutti,

devo realizzare una simulazione di un "labirinto". Ovvero, dato in ingresso un file txt con indicato il numero di vertici N (0 la partenza N-1 l'uscita) e gli archi, devo dire se è possibile uscire dal labirinto o no, se si indicare il cammino minimo (restituirò SI n) se no restituire NO -1.

ES di file:

4
0 1
0 2
1 3
2 3

In questo caso si può uscire dal labirinto e il cammino minimo è 2 quindi in output SI 2. Ovvio e banale nello svolgimento logico, un pò meno nello svolgimento in java (almeno per me). Se riesco a uscire non è un problema ho in mente come fare, il mio problema è il calcolo dei cammini minimi. Qualcun potrebbe darmi un indicazione? Non sto cercando una soluzione altrimenti non imparo nulla.

Grazie a tutti

[LeleFT]

Java ha un forum dedicato.
Sposto.

Nel frattempo, posta la soluzione che hai in mente per il caso del labirinto con uscita, così vediamo quali strutture dati hai pensato e come hai deciso di strutturare il codice.


Ciao.

[sabbia89]

Niente ho provato ma non riesco proprio. Non riesco a capire come "collegare" i vari nodi. Mi spiego meglio, inizialmente pensavo fosse sufficiente cercare vertice-1 all'interno del file per capire se l'uscita esistesse ma non basta, Non è sufficiente che l'uscita esista, ma deve essere anche collegata alla partenza, deve esiste un nodo (o,x), un nodo(x,y), e un nodo (y, vertice-1) o eventualmente nel caso migliore un nodo (0. vertice-1). Ho pensato a un ArrayList ma non saprei come poter gestire il collegamento.

[andbin]

4
0 1
0 2
1 3
2 3

Vorrei solo capire meglio il file: quindi a parte la riga iniziale, ogni riga è un arco, quindi ad esempio un arco tra 0 e 1?
E quindi una sequenza di uscita nell'esempio è 0-1 e 1-3, giusto? (quindi appunto 2 passi)

Comunque una possibilità è creare una struttura di oggetti in cui ogni oggetto è un nodo e può avere N riferimenti ad altri nodi. Pensa una cosa tipo una classe Nodo che contiene (oltre al numero) un List<Nodo> con riferimenti ad altri nodi.

[sabbia89]

Esattamente il concetto è proprio quello, se avessimo un file così:

4
01
02
12

non usciremmo dal labirinto. Provo a partorire qualcosa e ti faccio sapere grazie mille

[sabbia89]

Ho deciso di fare un array di liste concatenate di nodi. Per il momento sono arrivato fin qua:

public class ListaConcatenataDINodi {

// inner class della classe che definisce il nodo
    private class NodoLista{
        private String arco;
        private NodoLista collegamento;

//costruttore della classe innestata
        public NodoLista(){
collegamento = null;
            arco = null;
        }

//altro costruttore della classe NodoLista
        public NodoLista(String valoreArco, NodoLista valoreCollegamento){
collegamento = valoreCollegamento;
arco = valoreArco;
        }
    }

//creo un oggetto NodoLista per "referenziare" la posizione che all'inizio sarò in testa
    private NodoLista testa;

//costruttore della classe
    public ListaConcatenataDINodi(){
        testa = null;
    }

//metodo per determinare il numero di elementi nella lista
    public int lunghezza(){
intconteggio=0;
        NodoLista posizione = testa;
while(posizione!=null){
conteggio++;
posizione = posizione.collegamento;
        }
returnconteggio;
    }

//metodo per l'aggiunta in testa di un arco
    public void aggiungiInTesta(String arco){
        testa = new NodoLista(arco, testa);
    }

/*
     * metodo per la ricerca di un arco, in questo caso ho deciso di verificare se c'è "connesione" tra due nodi
       ovvero se tra (x1, y1) e (x2, y2): y1=x2. Se si aggiungi quel nodo in testa
    */
    private void trova (String arco){
        NodoLista posizione = testa;
        while(posizione != null){
            String arcoAllaPosizione = posizione.arco;
            char s = arcoAllaPosizione.charAt(0);
            char t = arco.charAt(3);
            if (s==t){
                aggiungiInTesta(arco);
            }
        }
    }

}

public class TabellaHash {
    private ListaConcatenataDINodi[] arrayHash;
privatestaticfinalintDIMENSIONE = 10;

//costruttore di classe
    public TabellaHash(){
        arrayHash = new ListaConcatenataDINodi[DIMENSIONE];
        for (int i= 0; i<DIMENSIONE ; i++){
            arrayHash[i]= new ListaConcatenataDINodi();
        }
    }

    public void aggiungi (String arco){

    }
}

La seconda classe si chiama TabellaHash perché inizialmente pensavo di usare il metodo hash per la ricerca della lista giusta, ma poi ho pensato che non può essere corretto perché io non devo cercare due nodi uguali, ma due nodi che abbiano un estremo di arco in comune, dato che è un grafo aciclico quindi (2,3) è uguale a (3,2).

Mi sono però bloccato perché non riesco a stabilire un criterio per cercare qual'è la lista giusta a cui inserire il nodo. Perché quel punto il metodo per la ricerca della lunghezza della lista c'è quindi mi basterebbe verificare con un metodo in quali liste è presente il nodo di uscita e a quel punto di quelle posso trovare la lunghezza e dare in output la lunghezza più piccola.


Naturalmente se qualcuno ha alternative più semplici/efficaci lo ascolto volentieri.