使用广度优先搜索的生成树出图？

Question

我正在尝试使用广度优先搜索来生成一个(生成)树，它是通过遍历一个图(无向和连通的)自然生成的，但是我很难修改算法来生成树。我用的是Java。

这是我的BFS算法。

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

我的图形数据结构很简单(注意它是无向和连通的) :

< code >公共类图{ Node mainNode...

树数据结构也很简单：

公共类树{Node root；..

我的节点是这样的：

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

我认为我的问题来自于我不能简单地将图中的某个< code >节点node直接添加到我的树中(因为这个< code >节点已经有了它的所有子节点)。相反，我必须创建一个< code >新节点(node.data)，这样树中添加的节点就不会指向图中相同节点将指向的所有相邻节点。

所以我的问题是:当使用广度优先搜索遍历所述图时，我如何从图中生成(生成)树？

Answer 1

我找到了一个简单的答案。我没有构建一棵树，而是删除了指向已经访问过的节点的边(这些信息是我们作为BFS算法的一部分免费获得的)。下面是我的实现(如果不想破坏最初的图形结构，它可能会被修改)。

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

编辑。下面是一个实现，它不会通过保持一个单独的队列来破坏初始的图形结构。

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

Answer 2

我将假设图既无向又有联系。话虽如此，我认为你走在正确的轨道上，但你还需要一些东西。首先，我强烈建议您将搜索状态和节点实现分开——换句话说，仅仅为了帮助您的搜索而存储私有成员变量Node.visible不是一个好主意。

您可以通过在搜索方法中维护一些额外的状态来避免这种情况，并使用递归私有帮助器方法对您的公共< code>traverse()方法的调用方隐藏该状态。为此，您需要在< code>Node类中正确实现< code>equals和< code>hashCode。

此外-如果您想创建一个具有不同节点的完全独立的树，则需要在图中创建每个节点的新的空实例，首先用对应节点的数据填充它们，然后使用克隆节点构建树。这就是说，这里有一些代码可以帮助您（我还没有测试过，但它应该让您知道该怎么做）：

/**
 * 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);
    }
}