Pages: [1]   Go Down
Print
Author Topic: spiegazione depth first search  (Read 2331 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« on: 30-05-2009, 17:50:32 »

qualcuno potrebbe spiegarmi il funzionamento dell'albero depth First search?
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #1 on: 31-05-2009, 10:23:45 »

non mi è chiara una cosa..la dfs dovrebbe servire per attraversare un grafo da quello che ho capito..infatti nelle slide stesse si parla di algoritmo dfs..ma perchè poi si implementa come una classe?non riesco a capire come si dovrebbe applicare...
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #2 on: 31-05-2009, 12:37:51 »

non mi è chiara una cosa..la dfs dovrebbe servire per attraversare un grafo da quello che ho capito..infatti nelle slide stesse si parla di algoritmo dfs..ma perchè poi si implementa come una classe?non riesco a capire come si dovrebbe applicare...

Di fatto bisogna fare uno sforzo di astrazione in più.
Per effettuare la DFS dovremmo dotare i nodi di default di un parametro "colore", utile per implementare l'algoritmo di attraversamento. Tuttavia questi parametri sarebbero "impropri" del grafo in sé stesso, poiché il nodo di un grafo, solitamente, non ha bisogno di un colore.
Quindi può avere senso separare la visita dal grafo, implementandola in una classe a parte, che si occupa di "allegare" al grafo tutti i parametri necessari al corretto funzionamento della visita.
Affinché la classe possa operare, è necessario che essa prenda come parametro un grafo, imposti le variabili accessorie e infine esegua il giusto algoritmo.
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #3 on: 01-06-2009, 11:04:45 »

ok ora ho capito...ma qualcuno ha un codice comprensibile e funzionante per la visita DFS???ho guardato le slide e il codice del prof ma non sono riuscita a capire certi metodi utilizzati da dove spuntano e a che servono anche perchè nelle classi non ci sono!!!
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #4 on: 01-06-2009, 15:04:50 »

Questa è la mia implementazione

Code:
class DFS {
private enum Stato {INESPLORATO, APERTO, CHIUSO }
private Grafo g;
private Stato[] st;
private Grafo.Vertice[] prev;

public DFS (Grafo _g) {
g = _g;
st = new Stato[g.getNumNodi()];
prev = new Grafo.Vertice[g.getNumNodi()];
}

public void visita() {
for (int i=0; i<g.getNumNodi(); i++) {
prev[i] = null;
st[i] = Stato.INESPLORATO;
}
for (int i=0; i<g.getNumNodi(); i++)
visita(g.getVertice(i));

for (int i=0; i<g.getNumNodi(); i++)
System.out.println(prev[i]);
}
public void visita(Grafo.Vertice x) {
st[g.getIndex(x)] = Stato.APERTO;
ListNode adiacente = x.adiac.getHead(); //prende il primo Vertice della lista di adiacenza di x
for (; adiacente != null; adiacente = adiacente.getNext() ) {
if (st[g.getIndex(adiacente.getInfo())] == Stato.INESPLORATO) {
prev[g.getIndex(adiacente.getInfo())] = x;
visita(adiacente.getInfo());

}

}
st[g.getIndex(x)] = Stato.CHIUSO;


}

}
l'algoritmo è lo stesso delle slide, cambiano i nomi dei metodi, quindi la lettura diciamo non è semplicissima...
Ad ogni modo getinfo() è usato per ritornare il valore contenuto nel nodo della lista e il valore contenuto nel nodo del grafo.
VList è la classe lista, ListNode il nodo, Grafo è il grafo e Vertice è il nodo del Grafo.

Se ci sono dubbi sono a disposizione.
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #5 on: 01-06-2009, 15:38:22 »

quello che soprattutto non ho capito io sono i vari tipi di getIndex..
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Eleirgab
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 344


Apprezzatemi ora. Eviterete la fila


WWW
« Reply #6 on: 01-06-2009, 18:43:03 »

Code:
g.getIndex(adiacente.getInfo())
Il metodo getIndex l'ho implementato nella casse Grafo e prende come parametro il Vertice.
Lo cerca nella lista dei nodi e ne restituisce l'indice.
Code:
adiacente.getInfo() // "estrae" dal ListNode il Vertice attualmente in esame
g.getIndex(adiacente.getInfo()) //ne recupera l'indice all'interno del grafo

Questo comando si ripete più volte. Sarebbe utile salvarlo in una variabile e richiamarlo, ma l'ho buttato giù di getto stamattina Cheesy

Spero che ora sia un pò più chiaro.
Logged

Collettivo SDAI

-----BEGIN GEEK CODE BLOCK-----
Version: 3.1
GIT d-- s+:+ a-- C++ UL++ P L+++ E- W+++>$ N? o? K- w-- O? M V? PS++ PE- Y+ PGP- t 5? X+ R>+ tv-- b++ DI+++ D- G e h! r y+
------END GEEK CODE BLOCK-----
Pages: [1]   Go Up
Print
Jump to: