I found a simple answer to my question. Instead of building a tree, I remove edges which lead to already visited nodes (this information we get for free as part of the BFS algorithm). Below is my implementation (it might be modified if one doesn't want to destroy the initial graph structure).
public static Tree BFS(Node node){
Queue queue= new Queue();
node.visited= true;
queue.enqueue(node);
while (!queue.isEmpty()){
Node r= queue.dequeue();
for (int i= 0; i < r.childen.size(); i++){
Node s= (Node)r.childen.get(i);
if (s.visited == false){
s.visited= true;
queue.enqueue(s);
}
else{
//Remove edge here
r.childen.remove(i);
i--;
}
}
}
Tree tree= new Tree(node);
return tree;
}
EDIT. The following is an implementation which doesn't destroy the initial graph structure by keeping a separate queue.
public static Tree BFS(Graph G, Node node){
Queue queue= new Queue();
Queue treeQueue= new Queue();
ArrayList<Node> tempV= new ArrayList<Node>();
tempV.add(node);
queue.enqueue(node);
Node root= new Node(node.data);
treeQueue.enqueue(root);
while (!queue.isEmpty()){
Node r= queue.dequeue();
Node t= treeQueue.dequeue();
for (int i= 0; i < r.childen.size(); i++){
Node s= (Node)r.childen.get(i);
if (tempV.indexOf(s) < 0){
tempV.add(s);
Node child= new Node(s.data);
t.childen.add(child);
queue.enqueue(s);
treeQueue.enqueue(child);
}
}
}
Tree tree= new Tree(root);
return tree;
}