使用广度优先搜索算法从图中生成一棵跨度树？

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

我的图数据结构如下（请注意它是无向且连通的）：

public class Graph { Node mainNode; ...

树数据结构也很简单：

public class Tree { Node root; ...

我的节点定义如下：

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

我认为我的问题在于我不能直接将图中的一些Node node添加到我的树中（因为这个node已经有了所有的子节点）。相反，我必须创建一个new Node(node.data)，以便在树中添加的节点不会指向同一节点在图中指向的所有相邻节点。所以我的问题是：在使用广度优先搜索遍历所述图时，如何构建出一棵（生成）树？

- under_the_sea_salad

---

我们可以假设这个图是无向且连通的吗？ - CodeBlind

是的，就是这样。 - under_the_sea_salad

Answer 1

我将假设图是无向且连通的。话虽如此，我认为你走在了正确的道路上，但你需要更多的东西。首先，我强烈建议您保持搜索状态和节点实现的分离，换句话说，存储私有成员变量Node.visible只是为了帮助您的搜索不是一个好主意。

您可以通过在搜索方法中维护一些额外的状态，并使用递归的私有辅助方法来隐藏该状态，使其不被公共traverse()方法的调用者看到。为此，您需要在Node类中正确实现equals和hashCode。

此外，如果您想创建一个完全独立的Tree并使用不同的节点，您需要在Graph中创建每个Node的新的空实例，并首先使用其对应方的数据填充它们，然后使用克隆的节点构建树。话虽如此，这里是一些代码让您开始（我没有测试过，但它应该给您一个大致的思路）：

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

- CodeBlind

---

谢谢你的回答。我认为我找到了一个更简单的实现方式，它不会偏离BFS算法太多。我删除了图中不必要的边，而不是构建一棵树。请查看我的答案。 - under_the_sea_salad

你说得很对，我不应该在Node类中将“visited”作为自己的字段。谢谢你的建议！ - under_the_sea_salad

Answer 2

我找到了一个简单的答案来回答我的问题。与其构建一棵树，我移除那些通往已经访问过的节点的边（这个信息可以在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;
}

- under_the_sea_salad