[JAVA] Stampa visita BFS e DFS

[Darèios89]

Sto provando a fare la stampa di queste visite in un grafo orientato implementato con liste di adiacenza, ma quando invoco la procedura mi restituisce sempre una stringa vuota, posto i codici con dei commenti, trascurate quelli relativi a cosa non indispensabili per le visite perché l' esercizio voleva altro:

La coda che mi serve per la BFS

public class Queue
{
	private GNode front;
	private GNode rear;
	private int size;
	
	public Queue()
	{
		front=rear=null;
		
		size=0;
	}
	
	public GNode getFront(){return front;}
	public GNode getRear(){return rear;}
	public int getSize(){return size;}
	
	public void enqueue(GNode node)
	{
		GNode nuovo=node;
		if(size==0)
			front=rear=nuovo;
		else{
			rear.setNext(nuovo);
			rear=nuovo;
			}
		size++;
	}
	
	public GNode dequeue()
	{
		if(size==0) return null;
		
		GNode tmp=getFront();
		front=tmp.getNext();
		tmp.setNext(null);
		size--;
		
		return tmp;
		
	}
}

La lista linkata dove inserirò i nodi del mio grafo:

public class LinkedList
{
	protected int size;
	protected GNode head;
	
	public LinkedList()
	{
		head=null;
		size=0;
		
	}
	
	public int getSize(){return size;}
	public GNode getHead(){return head;}
	public boolean isEmpty(){return (size==0);}
	public void addFirst(GNode node)        //inserimento in testa
	{
		if(isEmpty())
			head=node;
		else
		{			
			node.setNext(head);
			head=node;
		}
		
	   size++;
	}
}

La classe GNode del grafo:

public class GNode
{
	protected int label;
	protected Edge adiacent;
	protected int degree;
	protected GNode next;
	protected int color;
	protected int level;
	protected GNode parent;          //servirà per la visita BFS
	
	public GNode(int label)
	{
		this.label=label;
		adiacent=null;
		degree=0;
		next=null;
		color=0;
		level=-1;
		parent=null;
	}
	
	public void setParent(GNode node){parent=node;}
	public GNode getParent(){return parent;}
	public int getLevel(){return level;}
	public void setLevel(int i){level=i;}
	public int getColor(){return color;}
	public void setColor(int i){color=i;}
	public int getLabel(){return label;}
	public void setLabel(int label){this.label=label;}
	public int getDegree(){return degree;}
	public GNode getNext(){return next;}
	public void setNext(GNode next){this.next=next;}
	public void addAdiacent(GNode u)
	{
		Edge arco=new Edge(this, u);
		arco.setNext(adiacent);
		adiacent=arco;
		degree++;
	}
	
	public Edge getAdiacent(){return adiacent;}
	
	public String toString()
	{
		String ret="";
		return ret+=this.getLabel()+" ";
	}
	
}

La classe arco:

public class Edge
{
	private GNode origine;
	private GNode destinazione;
	private Edge next;
	
	public Edge(GNode origine, GNode destinazione)
	{
		this.origine=origine;
		this.destinazione=destinazione;
		next=null;
	}
	
	public GNode getOrigine(){return origine;}
	public GNode getDestinazione(){return destinazione;}
	public Edge getNext(){return next;}
	public void setNext(Edge next){this.next=next;}
	
}

E infine la classe Grafo:

public class Grafo
{
	protected LinkedList list;
	protected int node;
	protected int edges;
	protected String archi;        //APPOSITAMENTE PER QUESTO CASO
	protected Queue coda;      //Supporto per BFS
	protected String dfs="";    //Stamperò la DFS
	protected String bfs="";
	
	public Grafo()
	{
		coda=new Queue();
		list=new LinkedList();
		node=0;
		edges=0;
		archi="";                //APPOSITAMENTE PER QUESTO CASO
	}
	
	public int node(){return node;}
	public int edges(){return edges;}
	
	public void addEdge (GNode u, GNode v){
		u.addAdiacent(v);
		edges++;
	}
	
	public boolean isAdj(GNode u, GNode v)    //verifica se sono adiacenti
	{
		Edge arco=u.getAdiacent();
		
		while(arco!=null)
		{
			if(arco.getDestinazione()==v)
				return true;
			arco=arco.getNext();
		}
		return false;
	}
	
	public int degree(GNode u){return u.getDegree();}
		
	public void addNode(GNode nodo)
	{
		list.addFirst(nodo);
		node++;
	}
	
	public boolean isPresent(GNode nodo)   //verifica se un nodo è contenuto
	{
		GNode tmp=list.head;
		while(tmp!=null)
		{
			if(tmp.getLabel()==nodo.getLabel())
				return true;
			tmp=tmp.getNext();
		}
		
	  return false;
	}
	
	public void BFSVisit(GNode node)          
	{
		GNode nodo=list.head;
		
		while(nodo!=null)        //per tutti i nodi del grafo setto questi parametri
		{
			nodo.setColor(0);
			nodo.setLevel(-1);
			nodo.setParent(null);
			nodo=nodo.getNext();
		}
		
		node.setLevel(0);             //questo sarà il nodo da cui voglio iniziare la visita e setto così
		node.setColor(1);
		node.setParent(null);
		
		coda.enqueue(node);                 //inserisco in coda
		
		while(coda.getSize()>0){                    //qui tolgo l' elemento
			GNode s=coda.dequeue();
			//System.out.println(s.toString());
			bfs+=s.toString();                     //lo aggiungo alla stringa che mi stamperà la visita
			Edge arc=s.getAdiacent();         //prendo un arco
			while(arc!=null){                       //finchè arc non è null ho altri nodi adiacenti
				GNode dest=arc.getDestinazione();      //prendo il nodo adiacente e lo memorizzo in dest
				if(dest.getColor()==0)
				{
					coda.enqueue(dest);
					dest.setParent(s);
					dest.setLevel(s.getLevel()+1);
					dest.setColor(1);
				}
				arc=arc.getNext();    //avanzo per cercare gli altri archi e quindi i nodi adiacenti
			}
			    s.setColor(1);
		}
	}
	
	public void DFS()
	{
		GNode nodo=list.head;
		//Grafo corrente=this;
		
		while(nodo!=null)            //per ogni nodo setto di default
		{
			nodo.setColor(0);
			nodo.setParent(null);
			nodo=nodo.getNext();
		}
		
		GNode nodo1=list.head;
		
		while(nodo1!=null)
		{
			if(nodo1.getColor()==0)
				DFSVisit(/*corrente,*/nodo1);
			
			nodo1=nodo1.getNext();
		}
	}
	
	
	public void DFSVisit(/*Grafo g, */GNode s)
	{
		dfs+=s.toString();        //concateno la stringa che conterrà i valori
		s.setColor(1);
	
		Edge arc=s.getAdiacent();
		while(arc!=null)            //anche qui finchè ho nodi adiacenti se arc non uguale a null
		{
			GNode dest=arc.getDestinazione();      //trovo quello adiacente
			if(dest.getColor()==(0))
			{
				dest.setParent(s);
				DFSVisit(/*g,*/dest);
			}
			
			arc=arc.getNext();         //vado sugli altri archi cioè per cercare nodi adiacenti
		}
		s.setColor(2);
	}
		

	public String toStringDFS()
	{
		return dfs;
	}
	
	public String toStringBFS()
	{
		return bfs;
	}
}

Però in questo main ottengo due stringhe vuote come stampa:

public class GrafoOrientato
{
	public static void main(String []args)
	{
		Grafo gr=new Grafo();
		GNode nodo1=new GNode(10);
		GNode nodo2=new GNode(20);
		GNode nodo3=new GNode(30);
		GNode nodo4=new GNode(40);
		
		gr.addNode(nodo1);
		gr.addNode(nodo2);
		gr.addNode(nodo3);
		gr.addNode(nodo4);
		
	
		gr.addEdge(nodo4,nodo3);
		gr.addEdge(nodo3,nodo2);
		gr.addEdge(nodo2,nodo1);
		
		//System.out.println(gr.list.getHead().toString());
		System.out.println(gr.toStringBFS());
		System.out.println(gr.toStringDFS());
	}
}

Come mai mi stampa due stringhe vuote? Ho il sospetto che le chiamate ricorsive sovrascrivino male....come faccio a stampare?

[Darèios89]

Nessuno proprio potrebbe dare un' occhiata?