深度优先搜索/广度优先搜索易于实现

Question

List<Tree<T>> unvisited = node.getChildren();

DFS：

while (!unvisited.isEmpty()) {
   Tree<T> node = unvisited.remove(0);
   //search node
   unvisited.addAll(0, node.getChildren());
}

BFS：

while (!unvisited.isEmpty()) {
   Tree<T> node = unvisited.remove(0);
   //search node
   unvisited.addAll(node.getChildren());
}

这些实现是不是太简单而不是真的？在想我是不是漏掉了什么？

Answer 1

这些实现是不是太简单而不真实？在想我是不是漏掉了什么？

您的实现是正确的。

Answer 2

除非仅限于非循环图，否则您将在未访问列表中得到重复的节点，因为您尚未标记已访问的节点。在添加到树中之前，您需要遍历子列表并将其标记为已访问。

BFS伪码：http://en.wikipedia.org/wiki/Breadth-first_search#Pseudocode

此外，您可能想要考虑使用Deque来代替List。请参阅：http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html