java - 深さ優先探索/幅優先探索の簡単な実装

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

これらの実装は単純すぎて真実ではありませんか? 私は何かが足りないのだろうかと思っていましたか？

score 2 · Accepted Answer

非巡回グラフのみに限定されない限り、訪問したノードをマークしていないため、未訪問のリストにノードが重複することになります。ツリーに追加する前に、子のリストを反復処理し、訪問済みとしてマークする必要があります。

また、List の代わりに Deque を使用することも検討してください。参照: http://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

2 に答える 2