java - 深度优先搜索/广度优先搜索简单实现

Question

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

文件系统：

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

这些实现是否过于简单而令人难以置信？想知道我是否遗漏了什么？

score 2 · Accepted Answer

除非仅限于非循环图，否则您最终会在未访问列表中出现重复节点，因为您尚未标记已访问节点。在添加到树之前，您需要遍历子列表并标记它们已访问。

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

score 1 · Accepted Answer

这些实现是否过于简单而令人难以置信？想知道我是否遗漏了什么？

您的实现是正确的。

2 回答 2