Я решаю эту проблему dfs/bfs.
Я написал как итеративную версию, так и рекурсивную версию DFS.
Порядок посещения узла другой, и я не понимаю, почему.
итеративный поиск в глубину:
static void DFS (Integer root, Graph graph){
// System.out.println("DFS");
HashSet <Integer> explored = new HashSet<Integer>();
explored.add(root);
Stack<Integer> stack = new Stack<Integer>();
stack.add(root);
int v; int w;
while (!stack.isEmpty()){
v=stack.pop();
explored.add(v);
System.out.print(v + " ");
// for (int i=graph.adjacencies.get(v).size()-1; i>=0; i--) {
for (int i=0; i < graph.adjacencies.get(v).size(); i++) {
w = graph.adjacencies.get(v).get(i);
if (!explored.contains(w)){
stack.add(w);
explored.add(w);
}
}
}System.out.println();
}
рекурсивный поиск в глубину:
static void DFS_2 (Integer root, Graph graph){
// System.out.println("DFS_2");
int v; int w;
v = root;
graph.explored.add(v);
System.out.print(v + " ");
for (int i=0; i < graph.adjacencies.get(v).size(); i++) {
w = graph.adjacencies.get(v).get(i);
if (!graph.explored.contains(w)){
graph.explored.add(w);
DFS_2(w, graph);
}
}
}
Что касается учебной проблемы, мой вывод в итеративной версии DFS:
1 4 3 2 6
в то время как это должно быть (согласно выводу примера проблемы и рекурсивной версии):
1 3 2 6 4
Что тут происходит? Почему устранение рекурсии изменяет порядок посещенных узлов?