首页 文章

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

提问于
浏览 次
3

我正在尝试使用广度优先搜索来创建一个（跨越）树自然地来自遍历图形（未定向和连接），但是我在修改算法时遇到了困难，因此它会生成一棵树 . 我正在使用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) ，以便树中添加的节点不指向同一节点在图中指向的所有相邻节点 .

所以我的问题是：如何在使用广度优先搜索遍历所述图形的同时从图形中生成（跨越）树？

java algorithm graph tree breadth-first-search

2 回答

  • 1

    我'm going to operate off the assumption that the graph is both undirected and connected. That being said, I think 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'不是一个好主意存储私人成员变量 Node.visible 只是为了帮助您的搜索 .

    您可以通过在搜索方法中保留一些额外状态来避免这种情况，并使用递归私有帮助器方法从公共 traverse() 方法的调用方隐藏该状态 . 您需要在 Node 类中正确实现 equals 和 hashCode 才能执行此操作 .

    另外 - 如果你想要创建一个具有不同节点的完全独立的 Tree ，你基本上想要在 Graph 中创建每个 Node 的新的空实例，并首先用它们的对应物填充它们's data, then build the tree using the cloned nodes. That said, here' s一些代码让你去（I没有测试这个，但它应该让你知道该怎么做）：

    /**
 * 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);
    }
}
    回复于
  • 0

    我找到了一个简单的答案 . 我没有构建树，而是删除了导致已经访问过的节点的边缘（这些信息是我们作为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;
}
    回复于

相关问题