Spanning tree out of graph using Breadth First Search?

Question

I am trying to make a (spanning) tree that comes naturally from traversing a graph (undirected and connected) using Breadth First Search, but I am having difficulties modifying the algorithm such that it makes a tree. I am using Java.

Here is my BFS algorithm.

public void traverse(Node node){
    Queue queue= new Queue();
    node.visited= true;
    //Maybe do something here? 
    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){
                //And do something here? 
                s.visited= true;
                queue.enqueue(s);
            }
        }
    }
}

My graph data structure is simply this (note it's undirected and connected) :

public class Graph { Node mainNode; ...

And the tree data structure is also simply this:

public class Tree { Node root; ...

My Node is like this:

public class Node<T> {
    T data;
    boolean visited= false;
    ArrayList<Node> childen= new ArrayList<Node>();
    ...

I think my trouble comes from the fact that I can't simply add some Node node from the graph directly to my tree (because this node would have all its children already). Instead, I have to make a new Node(node.data) so that the added node in the tree doesn't point to all the adjacent nodes that the same node would point in the graph.

So my question: how do I make a (spanning) tree out of graph while traversing the said graph using Breadth First Search?

Answer 1

I'm going to operate off the assumption that the graph is both undirected and connected. That being said, I think you're on the right track, but you're going to need a few more things. First, I highly encourage you to keep your search state and node implementation separate - in other words, it's not a great idea to store a private member variable Node.visible just to aid your search.

You can avoid this by maintaining some extra state inside your search method, and use a recursive private helper method to hide that state from callers of your public traverse() method. You will need to properly implement equals and hashCode in your Node class to do this.

Also - if you are wanting to create a completely separate Tree with different nodes, you'll want to essentially create new, empty instances of each Node in the Graph and first populate them with their counterpart's data, then build the tree using the cloned nodes. That said, here's some code to get you going (I haven't tested this, but it should give you an idea of what to do):

/**
 * This facade method traverses just the root of the new tree.  All recursion is
 * passed to the "traverseHelper(3)" recursive method.
 */
public Tree<T> traverse(Graph<T> g){
    if(g == null || g.mainNode == null) return null;
    Node<T> node = g.mainNode;
    Node<T> clone = new Node<T>(node.data); //this is the root of our new Tree
    Set<Node<T>> searched = new HashSet<Node<T>>(); //accumulates searched nodes
    searched.add(node);
    traverseHelper(node,clone,searched);
    return new Tree<T>(clone);
}

/**
 * Recursively performs BFS on all the children of the specified node and its
 * corresponding cloned instance.
 *
 * Assumes that "node" has been added to "searched" and that 
 * "searched.contains(node)" AND "searched.contains(clone)" will return true by 
 * the time this method is called.
 */
private void traverseHelper(Node<T> node, Node<T> clone, Set<Node<T>> searched){
    if(node.children == null) return;
    Map<Node<T>,Node<T>> toRecurseOn = new HashMap<Node<T>,Node<T>>();

    //This is the Breadth-First part - builds the next leaves in the tree:
    for(Node<T> child : node.children){
        if(child == null || searched.contains(child)) continue;
        Node<T> childClone = new Node<T>(child.data); //create leaf in the tree
        clone.children.add(childClone); //builds the current level in the tree
        childClone.children.add(clone); //maintains undirected-ness of the tree
        toRecurseOn.put(child,childClone); //lets us BFS later
    }

    //This is the Search part - builds the subtrees:
    Iterator<Node<T>> i = toRecurseOn.keySet().iterator();
    while(i.hasNext()){
        Node<T> child = i.next();
        Node<T> childClone = toRecurseOn.get(child);
        i.remove(); //Saves a little memory throughout the recursion
        traverseHelper(child,childClone,searched);
    }
}

Answer 2

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;
}