Pages: [1]   Go Down
Print
Author Topic: DFS E BFS  (Read 1301 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« on: 20-07-2010, 07:54:04 »

Raga qualcuno di voi ha l'implementazione della dfs e bfs in java del professore?grazie ok
Logged

LexaIdo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 110



« Reply #1 on: 20-07-2010, 08:50:51 »

le hanno già postate qui  
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #2 on: 20-07-2010, 09:22:41 »

Vi sembra corretta questa visita?
Code:
DFS{
private enum stato {APERTO, INESPOLATO, CHIUSO};
    private grafo g;
    private nodografo [] prev;
    private stato [] st;
 
    public DFS(grafo g1){
        g = g1;
        st = new stato [g.getnodi().getsize()];
        prev = new nodografo [g.getnodi().getsize()];
    }
   
    public void visit(nodografo u){
        for(int i = 0; i < g.getnodi().getsize(); i++){
            st[i] = stato.INESPOLATO;
            prev[i] = null;
        }
        DFSvisit(u);
    }

    private void DFSvisit(nodografo u) {
        st[u.indice(g.getnodi())] = stato.APERTO;
        Nodon adj = u.getlistadiadiacenza().gethead();
        for(; adj != null; adj = adj.getnext()){
            if( st[adj.getdestinazione().indice(g.getnodi())] == stato.INESPOLATO){
                prev[adj.getdestinazione().indice(g.getnodi())] = u;
                DFSvisit( adj.getdestinazione());
            }
        }
        st[u.indice(g.getnodi())] = stato.CHIUSO;
    }
Logged

vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #3 on: 20-07-2010, 15:56:52 »

Vi sembra corretta questa visita?
Code:
DFS{
private enum stato {APERTO, INESPOLATO, CHIUSO};
    private grafo g;
    private nodografo [] prev;
    private stato [] st;
 
    public DFS(grafo g1){
        g = g1;
        st = new stato [g.getnodi().getsize()];
        prev = new nodografo [g.getnodi().getsize()];
    }
   
    public void visit(nodografo u){
        for(int i = 0; i < g.getnodi().getsize(); i++){
            st[i] = stato.INESPOLATO;
            prev[i] = null;
        }
        DFSvisit(u);
    }

    private void DFSvisit(nodografo u) {
        st[u.indice(g.getnodi())] = stato.APERTO;
        Nodon adj = u.getlistadiadiacenza().gethead();
        for(; adj != null; adj = adj.getnext()){
            if( st[adj.getdestinazione().indice(g.getnodi())] == stato.INESPOLATO){
                prev[adj.getdestinazione().indice(g.getnodi())] = u;
                DFSvisit( adj.getdestinazione());
            }
        }
        st[u.indice(g.getnodi())] = stato.CHIUSO;
    }
Se non mi sbaglio dovrebbe essere quella del professore Pulvirenti; mi sembra corretta.
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #4 on: 20-07-2010, 16:11:18 »

Code:
class nodo
{
public nodografo numero;
public nodo next;

public nodo(nodografo numero,nodo next)
{
this.numero=numero;
this.next=next;
}
public nodo(nodografo numero)
{
this.numero=numero;
this.next=null;
}
}
class linkedlist
{
public nodo head;
public int size;

public linkedlist()
{
head=null;
size=0;
}
public int getsize()
{
return size;
}
public nodografo get(int i)
{
nodo aux;
int gira=0;
for(aux=head;aux!=null && gira<i;aux=aux.next)
{
gira++;
}
return aux.numero;
}



public void insertail(nodografo n)
{
if (head==null)
head=new nodo(n);

else
{
nodo aux=head;
for(;aux.next!=null;aux=aux.next);
aux.next=new nodo(n);
}
size++;
}
public nodografo search(int num)
{
if( head==null)
return null;
else
{
nodo aux=head;
for(;aux!=null && aux.numero.numero!=num;aux=aux.next);
return aux.numero;
}
}
}
class nodografo
{
public int numero;
public linkedlist listadiadiacenza;
public nodografo(int numero)
{
this.numero=numero;
listadiadiacenza=new linkedlist();
}
public int indice(linkedlist l)
{
nodo aux;
int i=0;
for(aux=l.head;aux!=null && aux.numero.numero!=this.numero;aux=aux.next)
{
i++;
}
if(aux==null)return -1;
return i;
}
}
class grafo
{
public linkedlist nodi;
public grafo()
{
nodi=new linkedlist();
}
public int node()
{
return nodi.size;
}
public void aggiunginodografo(int numero)
{
nodi.insertail(new nodografo(numero));
}
public void aggiungiarco(nodografo p,nodografo d)
{
p.listadiadiacenza.insertail(d);
}
}
class DFS
{
private enum Stato{inesplorato,aperto,chiuso};
private grafo g;
private Stato [] st;
public nodografo [] prev;

public DFS(grafo g)
{
this.g=g;
st=new Stato[g.nodi.size];
prev=new nodografo[g.nodi.size];
}
public void visita()
{
for(int i=0;i<g.nodi.size;i++)
{
prev[i]=null;
st[i]=Stato.inesplorato;
}
DFSvisit(g.nodi.head.numero);

/*
for(int i=0;i<g.nodi.size;i++)
{
if(st[i]==Stato.inesplorato)
DFSvisit(g.nodi.get(i));
}
*/

/*for(int i=0;i<prev.length;i++)
{
if(prev[i]!=null) System.out.println(prev[i].numero);
}
*/

}
public void DFSvisit(nodografo u)
{
st[u.indice(g.nodi)]=Stato.aperto;
nodo aux=u.listadiadiacenza.head;
for(;aux!=null;aux=aux.next)
{
if(st[aux.numero.indice(g.nodi)]==Stato.inesplorato)
{
prev[aux.numero.indice(g.nodi)]=u;
// System.out.println(aux.numero.numero);
DFSvisit(aux.numero);
}
}
st[u.indice(g.nodi)]=Stato.chiuso;
}
public void printree(nodografo u)
{
System.out.println("null, "+ u.numero);

for(int i = 0; i < g.nodi.size; i++)
{
if(prev[i] != null)                           
System.out.println(prev[i].numero + ","+g.nodi.get(i).numero);

}
}
}


           
public class main
{
public static void main(String [] args)
{
grafo g=new grafo();
g.aggiunginodografo(1);
g.aggiunginodografo(2);
g.aggiunginodografo(3);
g.aggiunginodografo(4);
g.aggiunginodografo(5);

g.aggiungiarco(g.nodi.search(1),g.nodi.search(3));
g.aggiungiarco(g.nodi.search(1),g.nodi.search(4));
g.aggiungiarco(g.nodi.search(2),g.nodi.search(5));
g.aggiungiarco(g.nodi.search(2),g.nodi.search(1));
g.aggiungiarco(g.nodi.search(3),g.nodi.search(2));
g.aggiungiarco(g.nodi.search(3),g.nodi.search(1));
g.aggiungiarco(g.nodi.search(4),g.nodi.search(5));
g.aggiungiarco(g.nodi.search(4),g.nodi.search(3));
g.aggiungiarco(g.nodi.search(5),g.nodi.search(1));
g.aggiungiarco(g.nodi.search(5),g.nodi.search(2));
             //    System.out.println(g.nodi.search(3).listadiadiacenza.head.next.numero.numero);

DFS dfs =new DFS(g);
dfs.visita();
dfs.printree(g.nodi.search(1));




}
}
compilalo ed eseguilo,non capisco xkè mi dà i cammini sbagliati testate
Logged

vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #5 on: 20-07-2010, 16:39:58 »

ok ora lo compilo e ti faccio sapere.
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #6 on: 20-07-2010, 16:50:24 »

ok
Logged

vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #7 on: 20-07-2010, 16:53:37 »

Allora il risultato in uscita mi da questo :
Quote
null, 1
3,2
1,3
1,4
2,5
Te li da senza seguire un ordine. Non è che fai per caso l'inserimento dei nodi in testa? Perchè oggi sentivo un problema simile di un altro collega al ricevimento.
Logged
atrix0ne
Forumista
***
Offline Offline

Posts: 607


homo faber fortunae suae


« Reply #8 on: 20-07-2010, 17:01:16 »

no no l'inserimento lo faccio giusto in coda,cmq è giusta Wink l'ho provata nel foglio!

a te come sembra la dfs?visita tutti i nodi no?
Logged

Pages: [1]   Go Up
Print
Jump to: