Pages: [1]   Go Down
Print
Author Topic: aiuto Grafo con liste di adiacenza pesato: come implementarlo??  (Read 1484 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
kruger
Matricola
*
Offline Offline

Gender: Male
Posts: 47


benvenuti nel mio incubo...


WWW
« on: 30-08-2009, 15:40:53 »

Salve a tutti voi colleghi..
Nel sito del prof c'è l'ultimo pdf in cui ci sono alcuni progetti passati..
e buona parte di essi vogliono essere implementati con dei grafi con liste d adiacenza pesati.

dareste un'occhiata a questo codice??
Code:

public class Arco {
        protected NodoG y;
        protected Object peso;

        public Arco(NodoG y, Object weight)  {
                this.y = y;
                this.peso = weight;
        }
}


public void aggiungiArcoPesato(NodoG x, NodoG y, Object w) {
Arco a = new Arco(y,w);
x.adiacenza.addTail(a);
this.numArchi++;
}

non ho messo il nodo origine (NodoG x) nella classe Arco in quanto ho pensato di implementarne l'inserimento nel grafo nella maniera in cui ho scritto..
Secondo voi va bene?? grazie in anticipo..
Logged

Il vero signore è lento nel parlare e rapido nell'agire
Dhavamba
Apprendista Forumista
**
Offline Offline

Posts: 286


« Reply #1 on: 31-08-2009, 10:48:20 »

io l'ho fatto molto più semplice, siccome ogni nodo grafo ha una lista di nodi normali (che saranno sicuramente divversi dai nodi di altri nodi grafi), ho semplicemente aggiunto nella classe nodo un setpeso e un getpeso!!! spero che sono stato chiaro!!! Per esempio per un grafo non orientato nel mio modo un ipotetico metodo di inserisci arco pesato è:

Code:

public void InsertArco(Nodo_Grafo a, Nodo_Grafo b,int c) {
a.getLista().insertTail(b);
a.search(b.getInfo()).setPeso(c);
b.getLista().insertTail(a);
b.search(a.getInfo()).setPeso(c);
numArchi++;
}


e un ipotetico ritrovamento peso

Code:

public int PesoArco(Nodo_Grafo a, Nodo_Grafo b) {
return a.search(b.getInfo()).getPeso();
}


Spero di esserti stato d'aiuto!!!


P.S: Ovviamente nella classe node, il getInfo() e il getPeso() sono due cose distinte, uno dà il Nodo_Grafo (pensa ad un contenitore dentro un contenitore) e l'altro il peso...
« Last Edit: 31-08-2009, 10:55:33 by Dhavamba » Logged
kruger
Matricola
*
Offline Offline

Gender: Male
Posts: 47


benvenuti nel mio incubo...


WWW
« Reply #2 on: 31-08-2009, 14:52:31 »

si si, capito tutto grazie mille  yoh

sei stato utilissimo xD
Logged

Il vero signore è lento nel parlare e rapido nell'agire
Dhavamba
Apprendista Forumista
**
Offline Offline

Posts: 286


« Reply #3 on: 31-08-2009, 15:33:21 »

in bocca al lupo....ah, se hai il codice per il dfs con il grafico a matrice mi faresti un bel favore se lo mettessi
Logged
icemouse_ej
Guest
« Reply #4 on: 31-08-2009, 15:54:32 »

in bocca al lupo....ah, se hai il codice per il dfs con il grafico a matrice mi faresti un bel favore se lo mettessi

qui trovi qualcosa.. link
 

Code:
/**
 *
 * @author icemouse
 */
public class DFSMa {
    protected enum STATO{APERTO,CHIUSO,INESPLORATO}
    protected int numeroNodi;
    protected NodoG prev[];
    protected STATO st[];
    protected GrafoMa g;

    public DFSMa(GrafoMa _g){
        g=_g;
        numeroNodi=g.nodi.getSize();
        prev=new NodoG[numeroNodi];
        st=new STATO[numeroNodi];

    }
    public void visita(NodoG x){
        inizializzazione();
        visit(x);
        System.out.println("\nALBERO:\n");
        StampaAlbero(x);
    }

    public void inizializzazione(){
        int i=0;
        for(;i<numeroNodi;i++){
            prev[i]=null;
            st[i]=STATO.INESPLORATO;
        }
    }

    public void visit(NodoG x){
       
        st[x.getIndice(g.nodi)]=STATO.APERTO;

                         // x.getIndice(g.nodi) è implementato nella
                         // classe NodoG e restituisce l'indice i (numero intero),
                         // del nodo x..
       
        int j=0;
         
        for(;j<numeroNodi;j++)
            if(g.matrice[x.getIndice(g.nodi)][j]==1&&st[j]==STATO.INESPLORATO){
             
                prev[j]=x;
                visit(g.nodi.getNodo(j));
            }
        st[x.getIndice(g.nodi)]=STATO.CHIUSO;
    }

    public void StampaAlbero(NodoG x){
        System.out.println("null - "+x.info);
        for(int i=0;i<prev.length;i++){
            if(prev[i]!=null)
                System.out.println(prev[i].info+" - "+g.nodi.getNodo(i).info);
                                                     
                                                      \\ g.nodi.getNodo(i) è implementato nella
                                                      \\ classe Lista, e restituisce il nodoG di indice i.
        }

    }
}





Logged
Pages: [1]   Go Up
Print
Jump to: