关于DFS非递归实现
来源：3-9 非递归实现图的深度优先遍历
GameCater
2021-08-21
波波老师，我使用两个栈配合实现了和递归版本输出结果一样的DFS，有没有可以不需要辅助栈，可以反方向遍历当前顶点相邻顶点，然后让它们以适当的顺序入栈的方法？
// 这个实现中，相同的元素会多次入栈，在新元素入栈的同时标记该元素已访问，可以避免这个性能损耗
private void dfsNR(int v) {
Stack<Integer> stack = new Stack<>();
Deque<Integer> stack2 = new ArrayDeque<>();
stack.push(v);
while (!stack.isEmpty()) {
Integer cur = stack.pop();
if (visited[cur] == true) continue;
visited[cur] = true;
pre.add(cur);
for (int w : g.adj(cur))
if (!visited[w])
stack2.push(w);
while (!stack2.isEmpty())
stack.push(stack2.pop());
}
}
写回答
1回答
-
如果我没有理解错，你的问题的核心就是：如何在 Java 中反向遍历一个 TreeSet(或者 TreeMap)。
Java 中对于集合类都定义了正向和反向的迭代器。反向迭代器（descendingIterator）可以进行反向遍历。
对于 TreeSet，我写了一个简单的示例代码：
TreeSet<Integer> set = new TreeSet<>(); for(int i = 0; i < 10; i ++) set.add(i); Iterator<Integer> iter = set.descendingIterator(); while(iter.hasNext()){ System.out.println(iter.next()); }继续加油！：）
012021-08-22
相似问题