java - 使用广度优先搜索从图中生成树？

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)类图 { 节点主节点； ...

而树数据结构也很简单:

公共(public)类树 { 节点根； ...

我的节点是这样的:

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

我认为我的麻烦来自于我不能简单地将一些 Node 节点 从图中直接添加到我的树(因为这个 node 会拥有它的所有 child 已经)。相反，我必须制作一个 new Node(node.data) 以便树中添加的节点不会指向同一节点在图中指向的所有相邻节点。

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

Answer 1

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

您可以通过在搜索方法中维护一些额外的状态来避免这种情况，并使用递归的私有(private)辅助方法向公共(public) traverse() 的调用者隐藏该状态。方法。您将需要正确实现 equals和 hashCode在你的Node类来执行此操作。

此外 - 如果您想要创建一个完全独立的 Tree对于不同的节点，您实际上需要为每个 Node 创建新的空实例在Graph并首先用对方的数据填充它们，然后使用克隆的节点构建树。也就是说，这里有一些代码可以让您继续(我还没有测试过这个，但它应该让您知道该怎么做):

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