[JAVA] Implementazione algoritmi "Breadth-First / Depth-First Search"

[TommyGun]

Salve a tutti,
ho un piccolo (per voi) problema relativo all'implementazione di un esercizio che devo assolutamente fare per l'inizio della prossima settimana. Considerate che sono quasi a digiuno con java e sono quattro giorni che stò cercando di capire cosa bisogna fare e come, leggendo e rileggendo il testo che ho allegato di seguito.

Testo originale

Today you have to implement Breadth-First Search and Depth-First Search algorithms.
Breadth- and Depth-First searches only differ in the way their queuing functions work. Breadth-First Search queues new paths at the end of the queue (FIFO), whereas Depth-First Search queues new paths at the start of the queue (LIFO). Create 2 classes in your Eclipse package called BreadthFirstSearch and DepthFirstSearch and implement the searches (Hint: you can use a LinkedList to implement a Queue-see the Java API).
You should test your algorithms using a simple main class.
Create a simple tree by creating nodes and assigning children to them (minimum 7
nodes) e.g.
Node a = new Node("a");
Node b = new Node("b");
Node c = new Node("c");
a.addChild(b);
a.addChild(c);


Traduzione forzata!

Oggi dovete implementare la Breadth-First e Depth-First algo di ricerca.
Depth-First e Breadth-First differiscono soltanto nel trattamento della coda.
La ricerca Breadth-First aggiunge i nuovi percorsi all'estremità della coda (FIFO),
mentre la Depth-First aggiunge i nuovi percorsi all'inizio della coda (LIFO).
Generare 2 codici nel vostro Eclipse denominati BreadthFirstSearch e
DepthFirstSearch ed implementate le ricerche.
(suggerimento: potete usare una LinkedList per creare una Coda).
Dovreste verificare le vostre procedure usando un classe main semplice.
Creare un semplice albero generando i nodi ed assegnando i figli(minimo 7 nodi):
Node a = new Node("a");
Node b = new Node("b");
Node c = new Node("c");
a.addChild(b);
a.addChild(c);


Non riesco a capire come implementare ciò. Per le procedure di ricerca non ho problemi, ma per quanto riguarda le strutture dati da utilizzare e come utilizzarle si!
Cioè mi parla prima di coda, quindi suppongo di dover costruire una coda di Node utilizzando una LinkedList come lui stesso suggerisce di fare(anche qui se avete qualche esempio da mostrarmi sarebbe meglio!),
poi mi parla di alberi con relativo esempio, boh!
Qualsiasi suggerimento avete per cortesia postatelo,
stò affogando in un bicchier d'acqua!!

[TommyGun]

Scusate ma ho dimenticato di dire che il tipo Node deriva da una classe fornita con l'esercizio, dove sono anche implementati alcuni metodi per la gestione di liste, ma allora cosa dovrei creare utilizzando le LinkedList????
Boh, ancora più confusione!!!

Vi prego di postare qualche consiglio, sono sempre più disperato..

 import java.util.ArrayList;

public class Node {

	private ArrayList children;
	private String name;

	public Node(String name){
		children = new ArrayList();
		this.name = name;
	}

	public ArrayList getChildren(){
		return new ArrayList(children);
	}

	public Node addChild(Node child){
		children.add(child);
		return child;
	}

	public void removeChild(Node child){
		children.remove(child);
	}

	public String getName() {
		return name;
	}

	public boolean equals(Node other){
		return (this.getName().compareTo(other.getName())==0);
	}

	public boolean isEmpty(Node other){
		return (this == null);
	}
}

[TommyGun]

...ma non c'è più nessuna anima pia in questo forum?!?

[doraemon83]

La linked list ti serve per memorizzare l'ordine con cui visiti i nodi.

Per esempio per realizzare la BFS cioè la visita in ampiezza puoi realizzarla nel seguente modo in macropassi ( non ho tempo per fare il codice) :

1. Inserisci la radice nella linked list;
2. estrai il nodo in testa alla linked list, se il nodo esiste vai al punto 3, altrimenti vai al punto 7;
3. fai quello che devi fare sul nodo;
4. Aggiungi il figlio destro (se esiste) in coda alla linked list;
5. Aggiungi il figlio sinistro (se esiste) in coda alla linked list;
6. Torna al punto 2;
7. Fine.

Questo effettua la visita dell'albero per livello(ma anche di un generico grafo con i dovuti aggiustamenti), cioè prima la radice, poi tutti i nodi del primo livello, poi tutti quelli del secondo livello, ecc.

A te adattare questo algoritmo per fare la DFS

Qui puoi trovare un po di documentazione per le LinkedList

[TommyGun]

Ok, quindi provo a rimettere a posto le cose, dimmi se sbaglio.
La classe Node fornita dall'esercizio serve per costruire l'albero, quindi il riferimento dell'esercizio: costruite un semplice main...:
Node b = new Node("b");
Node c = new Node("c");
a.addChild(a);
a.addChild(b);
a.addChild(c)

sta' a dire che devo inserire all'interno della classe Node, per poter costruire l'albero, un main del tipo:

public static void main (String[] args) {
    Node a = new Node("a");
    Node b = new Node("b");
    Node c = new Node("c");
    a.addChild(a);
    a.addChild(b);
    a.addChild(c);
    } 

Ottenuto l'albero non devo far altro che implementare le due classi per la ricerca e quindi qui utilizzare le LinkedList per popolare le code.

Quindi l'albero avra' una struttura del tipo:

1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 ....
¦ ¦ ¦
2a 3a 6a
¦ ¦
2b 6b
¦
2c

**non so' la formattazione come verra' mostrata..

cosi' la visita in ampiezza sara': 1,2,3,4,5,6,7,8,9,2a,3a....
e la visita in profondita': 1,2,2a,2b,2c,3.....


Se e' cosi', grazie mille di nuovo per la tua risposta, altrimenti ti prego di correggermi...

Ciao ciao

[doraemon83]

Tutto giusto, e niente da aggiungere

buon lavoro

ciao ciao