非recursion深度优先searchalgorithm
我正在寻找一个非recursion深度searchalgorithm的非二叉树。 很感谢任何forms的帮助。
DFS：
list nodes_to_visit = {root}; while( nodes_to_visit isn't empty ) { currentnode = nodes_to_visit.take_first(); nodes_to_visit.prepend( currentnode.children ); //do something } BFS：
list nodes_to_visit = {root}; while( nodes_to_visit isn't empty ) { currentnode = nodes_to_visit.take_first(); nodes_to_visit.append( currentnode.children ); //do something }
两者的对称性非常好。
更新：正如指出的那样， take_first()移除并返回列表中的第一个元素。
您将使用一个包含尚未访问的节点的堆栈 ：
stack.push(root) while !stack.isEmpty() do node = stack.pop() for each node.childNodes do stack.push(stack) endfor // … endwhile
如果你有指向父节点的指针，你可以做到这一点，没有额外的内存。
def dfs(root): node = root while True: visit(node) if node.first_child: node = node.first_child # walk down else: while not node.next_sibling: if node is root: return node = node.parent # walk up ... node = node.next_sibling # ... and right
请注意，如果子节点被存储为一个数组而不是通过兄弟指针，那么可以find下一个兄弟节点：
def next_sibling(node): try: i = node.parent.child_nodes.index(node) return node.parent.child_nodes[i+1] except (IndexError, AttributeError): return None
使用堆栈来跟踪您的节点
Stack<Node> s; s.prepend(tree.head); while(!s.empty) { Node n = s.poll_front // gets first node // do something with q? for each child of n: s.prepend(child) }
虽然“使用堆栈” 可能会成为面试问题的答案，但事实上，它只是明确地在后台执行recursion程序。
recursion使用程序内置堆栈。 当你调用一个函数的时候，它会把这个函数的参数压入堆栈，当函数返回的时候通过popup程序堆栈来实现。
PreOrderTraversal is same as DFS in binary tree. You can do the same recursion taking care of Stack as below. public void IterativePreOrder(Tree root) { if (root == null) return; Stack s<Tree> = new Stack<Tree>(); s.Push(root); while (s.Count != 0) { Tree b = s.Pop(); Console.Write(b.Data + " "); if (b.Right != null) s.Push(b.Right); if (b.Left != null) s.Push(b.Left); } }
一般的逻辑是，将一个节点（从根开始）推入到Stack，Pop（）和Print（）值中。 然后，如果有孩子（左侧和右侧）将它们推入堆栈 – 先向右推，以便先访问左侧子节点（在访问节点本身之后）。 当堆栈为空（）时，您将访问预订中的所有节点。
假设您想要在graphics中的每个节点被访问时执行通知。 简单的recursion实现是：
void DFSRecursive(Node n, Set<Node> visited) { visited.add(n); for (Node x : neighbors_of(n)) { // iterate over all neighbors if (!visited.contains(x)) { DFSRecursive(x, visited); } } OnVisit(n); // callback to say node is finally visited, after all its non-visited neighbors }
好吧，现在你想要一个基于堆栈的实现，因为你的例子不起作用。 复杂的graphics可能会导致这种情况，导致程序堆栈崩溃，并且需要实现一个非recursion的版本。 最大的问题是要知道什么时候发出通知。
下面的伪代码工作（Java和C ++的可读性混合）：
void DFS(Node root) { Set<Node> visited; Set<Node> toNotify; // nodes we want to notify Stack<Node> stack; stack.add(root); toNotify.add(root); // we won't pop nodes from this until DFS is done while (!stack.empty()) { Node current = stack.pop(); visited.add(current); for (Node x : neighbors_of(current)) { if (!visited.contains(x)) { stack.add(x); toNotify.add(x); } } } // Now issue notifications. toNotifyStack might contain duplicates (will never // happen in a tree but easily happens in a graph) Set<Node> notified; while (!toNotify.empty()) { Node n = toNotify.pop(); if (!toNotify.contains(n)) { OnVisit(n); // issue callback toNotify.add(n); } }
它看起来很复杂，但是发出通知所需的额外逻辑存在，因为您需要以访问的相反顺序通知 – DFS从根开始，但最后通知它，不像BFS那么容易实现。
对于踢，请尝试下面的图：节点是s，t，v和w。 有向边是：s→t，s→v，t→w，v→w和v→t。 运行你自己的DFS实现，并且访问节点的顺序必须是：w，t，v，s一个笨拙的DFS实现可能会首先通知t并指出一个错误。 DFS的recursion实现将始终到达最后。
使用ES6生成器的非recursionDFS
class Node { constructor(name, childNodes) { this.name = name; this.childNodes = childNodes; this.visited = false; } } function *dfs(s) { let stack = []; stack.push(s); stackLoop: while (stack.length) { let u = stack[stack.length - 1]; // peek if (!u.visited) { u.visited = true; // grey - visited yield u; } for (let v of u.childNodes) { if (!v.visited) { stack.push(v); continue stackLoop; } } stack.pop(); // black - all reachable descendants were processed } }
它偏离典型的非recursionDFS，以便轻松检测给定节点的所有可访问后代何时被处理，并维护列表/堆栈中的当前path。
基于biziclops的ES6实现很棒的答案：
root = { text: "root", children: [{ text: "c1", children: [{ text: "c11" }, { text: "c12" }] }, { text: "c2", children: [{ text: "c21" }, { text: "c22" }] }, ] } console.log("DFS:") DFS(root, node => node.children, node => console.log(node.text)); console.log("BFS:") BFS(root, node => node.children, node => console.log(node.text)); function BFS(root, getChildren, visit) { let nodesToVisit = [root]; while (nodesToVisit.length > 0) { const currentNode = nodesToVisit.shift(); nodesToVisit = [ ...nodesToVisit, ...(getChildren(currentNode) || []), ]; visit(currentNode); } } function DFS(root, getChildren, visit) { let nodesToVisit = [root]; while (nodesToVisit.length > 0) { const currentNode = nodesToVisit.shift(); nodesToVisit = [ ...(getChildren(currentNode) || []), ...nodesToVisit, ]; visit(currentNode); } }
你可以使用堆栈。 我用Adjacency Matrix实现了图：
void DFS(int current){ for(int i=1; i<N; i++) visit_table[i]=false; myStack.push(current); cout << current << " "; while(!myStack.empty()){ current = myStack.top(); for(int i=0; i<N; i++){ if(AdjMatrix[current][i] == 1){ if(visit_table[i] == false){ myStack.push(i); visit_table[i] = true; cout << i << " "; } break; } else if(!myStack.empty()) myStack.pop(); } } }
Java中的DFS迭代：
//DFS: Iterative private Boolean DFSIterative(Node root, int target) { if (root == null) return false; Stack<Node> _stack = new Stack<Node>(); _stack.push(root); while (_stack.size() > 0) { Node temp = _stack.peek(); if (temp.data == target) return true; if (temp.left != null) _stack.push(temp.left); else if (temp.right != null) _stack.push(temp.right); else _stack.pop(); } return false; }
http://www.youtube.com/watch?v=zLZhSSXAwxI
只是看了这个video，实现了。 我很容易理解。 请批评这一点。
visited_node={root} stack.push(root) while(!stack.empty){ unvisited_node = get_unvisited_adj_nodes(stack.top()); If (unvisited_node!=null){ stack.push(unvisited_node); visited_node+=unvisited_node; } else stack.pop() }
使用Stack ，下面的步骤是：推动堆栈中的第一个顶点，
- 如果可能的话，访问邻近的未经访问的顶点，将其标记并将其推入堆栈。
- 如果不能按照步骤1进行操作，那么如果可能的话，从堆栈中popup一个顶点。
- 如果你不能按照步骤1或步骤2，就完成了。
以下是按照上述步骤的Java程序：
public void searchDepthFirst() { // begin at vertex 0 vertexList[0].wasVisited = true; displayVertex(0); stack.push(0); while (!stack.isEmpty()) { int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek()); // if no such vertex if (adjacentVertex == -1) { stack.pop(); } else { vertexList[adjacentVertex].wasVisited = true; // Do something stack.push(adjacentVertex); } } // stack is empty, so we're done, reset flags for (int j = 0; j < nVerts; j++) vertexList[j].wasVisited = false; }
Stack<Node> stack = new Stack<>(); stack.add(root); while (!stack.isEmpty()) { Node node = stack.pop(); System.out.print(node.getData() + " "); Node right = node.getRight(); if (right != null) { stack.push(right); } Node left = node.getLeft(); if (left != null) { stack.push(left); } }
