Als*_*ton 31 algorithm graph depth-first-search non-recursive
好吧,我花了很多时间在这个问题上.但是,我只能找到树的非递归方法的解决方案:树的非递归,或图的递归方法,图的递归.
许多教程(我不在这里提供这些链接)也没有提供方法.或者教程完全不正确.请帮我.
更新:
这很难描述:
如果我有一个无向图:
1
/ | \
4 | 2
3 /
1-- 2-- 3 - 1是一个循环.
在这一步: push the neighbors of the popped vertex into the stack
WHAT'S THE ORDER OF THE VERTEXES SHOULD BE PUSHED?
如果推送的顺序是2 4 3,则堆栈中的顶点是:
| |
|3|
|4|
|2|
_
弹出节点后,我们得到了结果:1 - > 3 - > 4 - > 2而不是1 - > 3 - > 2 - > 4.
这是不正确的.我应该添加什么条件来阻止这个场景？
ami*_*mit 46
没有递归的DFS与BFS基本相同- 但是使用堆栈而不是队列作为数据结构.
线程Iterative DFS vs Recursive DFS和不同的元素顺序处理两种方法和它们之间的区别(并且有!你不会以相同的顺序遍历节点!)
迭代方法的算法基本上是:
DFS(source):
s <- new stack
visited <- {} // empty set
s.push(source)
while (s is not empty):
current <- s.pop()
if (current is in visited):
continue
visited.add(current)
// do something with current
for each node v such that (current,v) is an edge:
s.push(v)
Pat*_*han 16
这不是一个答案,而是一个扩展的评论,显示算法在@ amit对问题当前版本中图形的回答中的应用,假设1是起始节点,其邻居按顺序推送2,4, 3:
1
/ | \
4 | 2
3 /
Actions Stack Visited
======= ===== =======
push 1 [1] {}
pop and visit 1 [] {1}
push 2, 4, 3 [2, 4, 3] {1}
pop and visit 3 [2, 4] {1, 3}
push 1, 2 [2, 4, 1, 2] {1, 3}
pop and visit 2 [2, 4, 1] {1, 3, 2}
push 1, 3 [2, 4, 1, 1, 3] {1, 3, 2}
pop 3 (visited) [2, 4, 1, 1] {1, 3, 2}
pop 1 (visited) [2, 4, 1] {1, 3, 2}
pop 1 (visited) [2, 4] {1, 3, 2}
pop and visit 4 [2] {1, 3, 2, 4}
push 1 [2, 1] {1, 3, 2, 4}
pop 1 (visited) [2] {1, 3, 2, 4}
pop 2 (visited) [] {1, 3, 2, 4}
因此,应用按顺序2,4,3顺序推送1的邻居的算法导致访问顺序1,3,2,4.无论1的邻居的推送顺序如何,2和3将在访问顺序中相邻,因为无论访问哪个首先将推动另一个尚未访问的,以及已访问过的另一个.
DFS逻辑应该是:
1)如果没有访问当前节点,请访问节点并将其标记为已访问
2)对于尚未访问的所有邻居,将它们推送到堆栈
例如,让我们用Java定义一个GraphNode类:
class GraphNode {
int index;
ArrayList<GraphNode> neighbors;
}
这是没有递归的DFS:
void dfs(GraphNode node) {
// sanity check
if (node == null) {
return;
}
// use a hash set to mark visited nodes
Set<GraphNode> set = new HashSet<GraphNode>();
// use a stack to help depth-first traversal
Stack<GraphNode> stack = new Stack<GraphNode>();
stack.push(node);
while (!stack.isEmpty()) {
GraphNode curr = stack.pop();
// current node has not been visited yet
if (!set.contains(curr)) {
// visit the node
// ...
// mark it as visited
set.add(curr);
}
for (int i = 0; i < curr.neighbors.size(); i++) {
GraphNode neighbor = curr.neighbors.get(i);
// this neighbor has not been visited yet
if (!set.contains(neighbor)) {
stack.push(neighbor);
}
}
}
}
我们可以使用相同的逻辑递归地执行DFS,克隆图等.
Many people will say that non-recursive DFS is just BFS with a stack rather than a queue. That's not accurate, let me explain a bit more.
Recursive DFS uses the call stack to keep state, meaning you do not manage a separate stack yourself.
However, for a large graph, recursive DFS (or any recursive function that is) may result in a deep recursion, which can crash your problem with a stack overflow (not this website, the real thing).
DFS is not the same as BFS. It has a different space utilization, but if you implement it just like BFS, but using a stack rather than a queue, you will use more space than non-recursive DFS.
Consider this:
// From non-recursive "DFS"
for (auto i&: adjacent) {
if (!visited(i)) {
stack.push(i);
}
}
And compare it with this:
// From recursive DFS
for (auto i&: adjacent) {
if (!visited(i)) {
dfs(i);
}
}
In the first piece of code you are putting all the adjacent nodes in the stack before iterating to the next adjacent vertex and that has a space cost. If the graph is large it can make a significant difference.
If you decide to solve the space problem by iterating over the adjacency list again after popping the stack, that's going to add time complexity cost.
One solution is to add items to the stack one by one, as you visit them. To achieve this you can save an iterator in the stack to resume the iteration after popping.
In C/C++, a lazy approach is to compile your program with a larger stack size and increase stack size via ulimit, but that's really lousy. In Java you can set the stack size as a JVM parameter.