[JAVA] Digrafo e nodi raggiungibili dal nodo sorgente

[Javino89]

Aspetta, chiariamo una cosa.

La dfs prevede un etichettatura dei vertici e degli archi come visitati. Per la precisione gli archi si dividono
in back-edge (archi all'indietro, ti portano in un nodo già visitato) e discovery-edge (ti portano in nodi non visitati).

Siccome a me i vertici sono semplici interi, e la classe Edge5R non prevede un campo per l'etichettatura
ho creato le liste e_visited (per metterci gli archi che visito) ed v_visited (per metterci i nodi che visito).

Io devo ritornare una Set<Integer> dei nodi che incontro secondo il vincolo di attraversare massimo int max archi.

Ora che me lo fai notare è inutile tenere entrambe le liste (v_visited e ris)... credo.

Il problema è che scrivendo cont = 1 + dfs(....) il metodo non può avere void come tipo di ritorno ma int e la cosa mi porta problemi poiché il metodo era pensato per fare side-effect sulla lista Set<Integer> ris. Inoltre cont dovrebbe azzerarsi una volta che il ciclo for principale esegue una iterazione..

[Javino89]

Ho capito. La notte porta consiglio. La strada che ho scelto è indubbiamente più complessa del normale. La soluzione è come ho detto qualche risposta sopra, utilizzare la BFS e non la DFS. La BFS intanto non è ricorsiva, un problema in meno. Inoltre per sua stessa natura si adatta perfettamente al problema in questione. La BFS infatti effettua una visita in ampiezza
aggiungendo ad una coda FIFO tutti i nodi raggiungibili a livello 1 (a distanza 1 dal nodo di partenza), poi tutti i nodi
a livello 2 e così via. Basta specializzare questa BFS in modo tale da fermarla quando arriviamo al livello max

Vediamo se riesco..