# 非recursion深度优先searchalgorithm

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 }` `

` `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` `

` `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使用程序内置堆栈。 当你调用一个函数的时候，它会把这个函数的参数压入堆栈，当函数返回的时候通过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); } }` `

` `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 }` `

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

` `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 } }` `

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

` `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; }` `

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

1. 如果可能的话，访问邻近的未经访问的顶点，将其标记并将其推入堆栈。
2. 如果不能按照步骤1进行操作，那么如果可能的话，从堆栈中popup一个顶点。
3. 如果你不能按照步骤1或步骤2，就完成了。

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