Java中的广度和深度优先搜索

Question

BFS和DFS在Java中的应用。请给出建议！！

Class Main {
    public void bfs()
    {
        // BFS uses Queue data structure
        Queue queue = new LinkedList();
        queue.add(this.rootNode);
        printNode(this.rootNode);
        rootNode.visited = true;
        while(!queue.isEmpty()) {
            Node node = (Node)queue.remove();
            Node child=null;
            while((child=getUnvisitedChildNode(node))!=null) {
                child.visited=true;
                printNode(child);
                queue.add(child);
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }

    public void dfs() {
        // DFS uses Stack data structure
        Stack stack = new Stack();
        stack.push(this.rootNode);
        rootNode.visited=true;
        printNode(rootNode);
        while(!stack.isEmpty()) {
            Node node = (Node)s.peek();
            Node child = getUnvisitedChildNode(n);
            if(child != null) {
                child.visited = true;
                printNode(child);
                s.push(child);
            }
            else {
                s.pop();
            }
        }
        // Clear visited property of nodes
        clearNodes();
    }
}


Class Node {
   Char data;
   Public Node(char c) {
      this.data=c;
   }
}

Answer 1

这里似乎有些矛盾。s是什么？我猜这就是那堆？同时声明一个类Main也有点奇怪。你当然想要一个主要的方法，但一个主要的类？

另外，我建议您不要使用原始集合，例如替换

Queue queue = new LinkedList();

使用

Queue<Node> queue = new LinkedList<Node>();

您可能会考虑递归地实现DFS，这样您就不必显式地使用堆栈，尽管这是一个品味问题。另外，getUnvisitedChildNode()是在哪里定义的？图的边缘实际上存储在哪里？这可能是一个邻接列表，由每个节点，或可能在另一个对象，但它应该在某处。

Answer 2

最好将函数命名为广度优先遍历或深度优先遍历，因为您没有查找任何元素，而是遍历了所有节点。(不过，相当琐碎:)

Answer 3

LinkedList支持堆栈操作和队列操作。所以这两种情况你都可以用。另外，如果您使用的是Java 6+，最好使用Deque接口而不是队列。(Deque扩展队列)。

因此，您的堆栈和队列声明应该如下所示(对于Java 6+ )

Deque<Node> queue = new LinkedList<Node>();
Deque<Node> stack = new LinkedList<Node>();