blocks|key|971116|text|您将使用包含尚未访问的节点的stack：|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|971117|stack.push(root)
while+!stack.isEmpty()+do
++++node+=+stack.pop()
++++for+each+node.childNodes+do
++++++++stack.push(stack)
++++endfor
++++//+…
endwhile|code-block|syntax|javascript|971118|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Stack_%2528data_structure%2529^0|E|5|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

You would use a <a href="http://en.wikipedia.org/wiki/Stack_%28data_structure%29">stack</a> that holds the nodes that were not visited yet:

<pre><code>stack.push(root)
while !stack.isEmpty() do
 node = stack.pop()
 for each node.childNodes do
 stack.push(stack)
 endfor
 // …
endwhile
</code></pre>

blocks|key|971208|text|如果您有指向父节点的指针，则无需额外内存即可完成此操作。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|971209|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|code-block|syntax|javascript|971210|请注意，如果子节点存储为数组，而不是通过同级指针，则可以找到下一个同级节点：|971211|def+next_sibling(node):
++++try:
++++++++i+=++++node.parent.child_nodes.index(node)
++++++++return+node.parent.child_nodes[i%2B1]
++++except+(IndexError,+AttributeError):
++++++++return+None|971212|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

If you have pointers to parent nodes, you can do it without additional memory.

<pre><code>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
</code></pre>

Note that if the child nodes are stored as an array rather than through sibling pointers, the next sibling can be found as:

<pre><code>def next_sibling(node):
 try:
 i = node.parent.child_nodes.index(node)
 return node.parent.child_nodes[i+1]
 except (IndexError, AttributeError):
 return None
</code></pre>

blocks|key|755502|text|使用堆栈跟踪节点|type|unstyled|depth|inlineStyleRanges|entityRanges|data|755503|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)

}|code-block|syntax|javascript|755504|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Use a stack to track your nodes

<pre><code>Stack&lt;Node&gt; 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)

}
</code></pre>

blocks|key|756206|text|一个基于biziclops的ES6实现很好的答案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|756207|​|756208|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)+%7C%7C+[]),
++++];
++++visit(currentNode);
++}
}

function+DFS(root,+getChildren,+visit)+{
++let+nodesToVisit+=+[root];
++while+(nodesToVisit.length+>+0)+{
++++const+currentNode+=+nodesToVisit.shift();
++++nodesToVisit+=+[
++++++...(getChildren(currentNode)+%7C%7C+[]),
++++++...nodesToVisit,
++++];
++++visit(currentNode);
++}
}|code-block|syntax|javascript|756209|756210|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|N|8|@]|9|@]|A|$G|H]]|$1|I|3|C|5|6|7|O|8|@]|9|@]|A|$]]|$1|J|3|-4|5|6|7|P|8|@]|9|@]|A|$]]]|K|$]]

An ES6 implementation based on biziclops great answer:

<div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false">
<div class="snippet-code">
<pre class="snippet-code-js lang-js prettyprint-override"><code>root = {
 text: "root",
 children: [{
 text: "c1",
 children: [{
 text: "c11"
 }, {
 text: "c12"
 }]
 }, {
 text: "c2",
 children: [{
 text: "c21"
 }, {
 text: "c22"
 }]
 }, ]
}

console.log("DFS:")
DFS(root, node =&gt; node.children, node =&gt; console.log(node.text));

console.log("BFS:")
BFS(root, node =&gt; node.children, node =&gt; console.log(node.text));

function BFS(root, getChildren, visit) {
 let nodesToVisit = [root];
 while (nodesToVisit.length &gt; 0) {
 const currentNode = nodesToVisit.shift();
 nodesToVisit = [
 ...nodesToVisit,
 ...(getChildren(currentNode) || []),
 ];
 visit(currentNode);
 }
}

function DFS(root, getChildren, visit) {
 let nodesToVisit = [root];
 while (nodesToVisit.length &gt; 0) {
 const currentNode = nodesToVisit.shift();
 nodesToVisit = [
 ...(getChildren(currentNode) || []),
 ...nodesToVisit,
 ];
 visit(currentNode);
 }
}</code></pre>
</div>
</div>

blocks|key|971313|text|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+%2B+"+");
++++++++++++++++++++if+(b.Right+!=+null)
++++++++++++++++++++++++s.Push(b.Right);
++++++++++++++++++++if+(b.Left+!=+null)
++++++++++++++++++++++++s.Push(b.Left);

++++++++++++++++}
++++++++++++}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|971314|一般的逻辑是，将一个节点(从根开始)推入Stack，Pop()它和Print()值。然后，如果它有子节点(左和右)，则将它们推入堆栈-先推入右，这样您将首先访问左子节点(在访问节点本身之后)。当stack为空()时，您将按预定顺序访问所有节点。|unstyled|971315|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$B|C]]|$1|D|3|E|5|F|7|J|8|@]|9|@]|A|$]]|$1|G|3|-4|5|F|7|K|8|@]|9|@]|A|$]]]|H|$]]

<pre><code>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&lt;Tree&gt; = new Stack&lt;Tree&gt;();
 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);

 }
 }
</code></pre>

The general logic is, push a node(starting from root) into the Stack, Pop() it and Print() value. Then if it has children( left and right) push them into the stack - push Right first so that you will visit Left child first(after visiting node itself). When stack is empty() you will have visited all nodes in Pre-Order.

blocks|key|971583|text|使用ES6生成器的非递归DFS|type|unstyled|depth|inlineStyleRanges|entityRanges|data|971584|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+
++}++++
}|code-block|syntax|javascript|971585|它与typical+non-recursive+DFS背道而驰，以便于检测给定节点的所有可达后代何时被处理，并维护列表/堆栈中的当前路径。|offset|length|971586|entityMap|0|LINK|mutability|MUTABLE|url|https://en.wikipedia.org/wiki/Depth-first_search^0|0|0|2|P|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@$I|V|J|W|1|X]]|A|$]]|$1|K|3|-4|5|6|7|Y|8|@]|9|@]|A|$]]]|L|$M|$5|N|O|P|A|$Q|R]]]]

Non-recursive DFS using ES6 generators

<pre class="lang-js prettyprint-override"><code>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 
 } 
}
</code></pre>

It deviates from <a href="https://en.wikipedia.org/wiki/Depth-first_search" rel="nofollow">typical non-recursive DFS</a> to easily detect when all reachable descendants of given node were processed and to maintain the current path in the list/stack.

blocks|key|971463|text|假设您想要在访问图中的每个节点时执行通知。简单的递归实现是：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|971464|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
}|code-block|syntax|javascript|971465|好了，现在你想要一个基于堆栈的实现，因为你的例子不能工作。例如，复杂的图形可能会导致程序的堆栈崩溃，您需要实现一个非递归版本。最大的问题是知道何时发出通知。|971466|下面的伪代码可以工作(为了提高可读性，混合使用Java和C%2B%2B+)：|971467|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);
++}
}|971468|它看起来很复杂，但发出通知所需的额外逻辑是存在的，因为您需要以相反的访问顺序通知-+DFS从根目录开始，但最后通知它，而不像BFS，它非常容易实现。|971469|为了提高效率，请尝试下面的图:节点是s，t，v和w。有向边是:+s->t，s->v，t->w，v->w和v->t。运行您自己的DFS实现，访问节点的顺序必须是:+w，t，v，s。笨拙的DFS实现可能会首先通知t，这表明存在错误。DFS的递归实现总是最后达到w。|971470|entityMap^0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|T|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|U|8|@]|9|@]|A|$]]|$1|I|3|J|5|6|7|V|8|@]|9|@]|A|$]]|$1|K|3|L|5|D|7|W|8|@]|9|@]|A|$E|F]]|$1|M|3|N|5|6|7|X|8|@]|9|@]|A|$]]|$1|O|3|P|5|6|7|Y|8|@]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|Z|8|@]|9|@]|A|$]]]|R|$]]

Suppose you want to execute a notification when each node in a graph is visited. The simple recursive implementation is:

<pre><code>void DFSRecursive(Node n, Set&lt;Node&gt; 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
}
</code></pre>

Ok, now you want a stack-based implementation because your example doesn't work. Complex graphs might for instance cause this to blow the stack of your program and you need to implement a non-recursive version. The biggest issue is to know when to issue a notification.

The following pseudo-code works (mix of Java and C++ for readability):

<pre><code>void DFS(Node root) {
 Set&lt;Node&gt; visited;
 Set&lt;Node&gt; toNotify; // nodes we want to notify

 Stack&lt;Node&gt; 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&lt;Node&gt; notified;
 while (!toNotify.empty()) {
 Node n = toNotify.pop();
 if (!toNotify.contains(n)) {
 OnVisit(n); // issue callback
 toNotify.add(n);
 }
}
</code></pre>

It looks complicated but the extra logic needed for issuing notifications exists because you need to notify in reverse order of visit - DFS starts at root but notifies it last, unlike BFS which is very simple to implement.

For kicks, try following graph:
nodes are s, t, v and w.
directed edges are:
s->t, s->v, t->w, v->w, and v->t.
Run your own implementation of DFS and the order in which nodes should be visited must be:
w, t, v, s
A clumsy implementation of DFS would maybe notify t first and that indicates a bug. A recursive implementation of DFS would always reach w last.

blocks|key|756302|text|完整的示例工作代码，没有堆栈：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|756303|import+java.util.*;

class+Graph+{
private+List<List<Integer>>+adj;

Graph(int+numOfVertices)+{
++++this.adj+=+new+ArrayList<>();
++++for+(int+i+=+0;+i+<+numOfVertices;+%2B%2Bi)
++++++++adj.add(i,+new+ArrayList<>());
}

void+addEdge(int+v,+int+w)+{
++++adj.get(v).add(w);+//+Add+w+to+v's+list.
}

void+DFS(int+v)+{
++++int+nodesToVisitIndex+=+0;
++++List<Integer>+nodesToVisit+=+new+ArrayList<>();
++++nodesToVisit.add(v);
++++while+(nodesToVisitIndex+<+nodesToVisit.size())+{
++++++++Integer+nextChild=+nodesToVisit.get(nodesToVisitIndex%2B%2B);//+get+the+node+and+mark+it+as+visited+node+by+inc+the+index+over+the+element.
++++++++for+(Integer+s+:+adj.get(nextChild))+{
++++++++++++if+(!nodesToVisit.contains(s))+{
++++++++++++++++nodesToVisit.add(nodesToVisitIndex,+s);//+add+the+node+to+the+HEAD+of+the+unvisited+nodes+list.
++++++++++++}
++++++++}
++++++++System.out.println(nextChild);
++++}
}

void+BFS(int+v)+{
++++int+nodesToVisitIndex+=+0;
++++List<Integer>+nodesToVisit+=+new+ArrayList<>();
++++nodesToVisit.add(v);
++++while+(nodesToVisitIndex+<+nodesToVisit.size())+{
++++++++Integer+nextChild=+nodesToVisit.get(nodesToVisitIndex%2B%2B);//+get+the+node+and+mark+it+as+visited+node+by+inc+the+index+over+the+element.
++++++++for+(Integer+s+:+adj.get(nextChild))+{
++++++++++++if+(!nodesToVisit.contains(s))+{
++++++++++++++++nodesToVisit.add(s);//+add+the+node+to+the+END+of+the+unvisited+node+list.
++++++++++++}
++++++++}
++++++++System.out.println(nextChild);
++++}
}

public+static+void+main(String+args[])+{
++++Graph+g+=+new+Graph(5);

++++g.addEdge(0,+1);
++++g.addEdge(0,+2);
++++g.addEdge(1,+2);
++++g.addEdge(2,+0);
++++g.addEdge(2,+3);
++++g.addEdge(3,+3);
++++g.addEdge(3,+1);
++++g.addEdge(3,+4);

++++System.out.println("Breadth+First+Traversal-+starting+from+vertex+2:");
++++g.BFS(2);
++++System.out.println("Depth+First+Traversal-+starting+from+vertex+2:");
++++g.DFS(2);
}}|code-block|syntax|javascript|756304|输出:广度第一遍历-从顶点2:+2+0+3+1+4深度第一遍历-从顶点2:+2+3+4+1+0开始|756305|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

FULL example WORKING code, without stack:

<pre><code>import java.util.*;

class Graph {
private List&lt;List&lt;Integer&gt;&gt; adj;

Graph(int numOfVertices) {
 this.adj = new ArrayList&lt;&gt;();
 for (int i = 0; i &lt; numOfVertices; ++i)
 adj.add(i, new ArrayList&lt;&gt;());
}

void addEdge(int v, int w) {
 adj.get(v).add(w); // Add w to v's list.
}

void DFS(int v) {
 int nodesToVisitIndex = 0;
 List&lt;Integer&gt; nodesToVisit = new ArrayList&lt;&gt;();
 nodesToVisit.add(v);
 while (nodesToVisitIndex &lt; nodesToVisit.size()) {
 Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
 for (Integer s : adj.get(nextChild)) {
 if (!nodesToVisit.contains(s)) {
 nodesToVisit.add(nodesToVisitIndex, s);// add the node to the HEAD of the unvisited nodes list.
 }
 }
 System.out.println(nextChild);
 }
}

void BFS(int v) {
 int nodesToVisitIndex = 0;
 List&lt;Integer&gt; nodesToVisit = new ArrayList&lt;&gt;();
 nodesToVisit.add(v);
 while (nodesToVisitIndex &lt; nodesToVisit.size()) {
 Integer nextChild= nodesToVisit.get(nodesToVisitIndex++);// get the node and mark it as visited node by inc the index over the element.
 for (Integer s : adj.get(nextChild)) {
 if (!nodesToVisit.contains(s)) {
 nodesToVisit.add(s);// add the node to the END of the unvisited node list.
 }
 }
 System.out.println(nextChild);
 }
}

public static void main(String args[]) {
 Graph g = new Graph(5);

 g.addEdge(0, 1);
 g.addEdge(0, 2);
 g.addEdge(1, 2);
 g.addEdge(2, 0);
 g.addEdge(2, 3);
 g.addEdge(3, 3);
 g.addEdge(3, 1);
 g.addEdge(3, 4);

 System.out.println("Breadth First Traversal- starting from vertex 2:");
 g.BFS(2);
 System.out.println("Depth First Traversal- starting from vertex 2:");
 g.DFS(2);
}}
</code></pre>

output:
Breadth First Traversal- starting from vertex 2:
2
0
3
1
4
Depth First Traversal- starting from vertex 2:
2
3
4
1
0

blocks|key|755654|text|http://www.youtube.com/watch?v=zLZhSSXAwxI|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|755655|我刚刚看了这个视频，并提出了实现方案。我看起来很容易理解。请对此进行评论。|755656|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%2B=unvisited_node;
++}
++else
+++++stack.pop()
}|code-block|syntax|javascript|755657|entityMap|0|LINK|mutability|MUTABLE|url^0|0|16|0|0|0|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@$A|S|B|T|1|U]]|C|$]]|$1|D|3|E|5|6|7|V|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|W|8|@]|9|@]|C|$I|J]]|$1|K|3|-4|5|6|7|X|8|@]|9|@]|C|$]]]|L|$M|$5|N|O|P|C|$Q|4]]]]

<a href="http://www.youtube.com/watch?v=zLZhSSXAwxI" rel="nofollow">http://www.youtube.com/watch?v=zLZhSSXAwxI</a>

Just watched this video and came out with implementation. It looks easy for me to understand. Please critique this.

<pre><code>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()
}
</code></pre>

blocks|key|971370|text|您可以使用堆栈。我使用邻接矩阵实现了图：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|971371|void+DFS(int+current){
++++for(int+i=1;+i<N;+i%2B%2B)+visit_table[i]=false;
++++myStack.push(current);
++++cout+<<+current+<<+"++";
++++while(!myStack.empty()){
++++++++current+=+myStack.top();
++++++++for(int+i=0;+i<N;+i%2B%2B){
++++++++++++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();
++++++++}
++++}
}|code-block|syntax|javascript|971372|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

You can use a stack. I implemented graphs with Adjacency Matrix:

<pre><code>void DFS(int current){
 for(int i=1; i&lt;N; i++) visit_table[i]=false;
 myStack.push(current);
 cout &lt;&lt; current &lt;&lt; " ";
 while(!myStack.empty()){
 current = myStack.top();
 for(int i=0; i&lt;N; i++){
 if(AdjMatrix[current][i] == 1){
 if(visit_table[i] == false){ 
 myStack.push(i);
 visit_table[i] = true;
 cout &lt;&lt; i &lt;&lt; " ";
 }
 break;
 }
 else if(!myStack.empty())
 myStack.pop();
 }
 }
}
</code></pre>

blocks|key|971500|text|Java中的DFS迭代：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|971501|//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;
}|code-block|syntax|javascript|971502|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

DFS iterative in Java:

<pre><code>//DFS: Iterative
private Boolean DFSIterative(Node root, int target) {
 if (root == null)
 return false;
 Stack&lt;Node&gt; _stack = new Stack&lt;Node&gt;();
 _stack.push(root);
 while (_stack.size() &gt; 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;
}
</code></pre>

blocks|key|971982|text|我只是想把我的python实现添加到长长的解决方案列表中。这个非递归算法有发现和完成的事件。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|971983|worklist+=+[root_node]
visited+=+set()
while+worklist:
++++node+=+worklist[-1]
++++if+node+in+visited:
++++++++#+Node+is+finished
++++++++worklist.pop()
++++else:
++++++++#+Node+is+discovered
++++++++visited.add(node)
++++++++for+child+in+node.children:
++++++++++++worklist.append(child)|code-block|syntax|javascript|971984|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Just wanted to add my python implementation to the long list of solutions. This non-recursive algorithm has discovery and finished events.

<pre class="lang-py prettyprint-override"><code>
worklist = [root_node]
visited = set()
while worklist:
 node = worklist[-1]
 if node in visited:
 # Node is finished
 worklist.pop()
 else:
 # Node is discovered
 visited.add(node)
 for child in node.children:
 worklist.append(child)
</code></pre>

blocks|key|971858|text|Stack<Node>+stack+=+new+Stack<>();
stack.add(root);
while+(!stack.isEmpty())+{
++++Node+node+=+stack.pop();
++++System.out.print(node.getData()+%2B+"+");

++++Node+right+=+node.getRight();
++++if+(right+!=+null)+{
++++++++stack.push(right);
++++}

++++Node+left+=+node.getLeft();
++++if+(left+!=+null)+{
++++++++stack.push(left);
++++}
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|971859|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>Stack&lt;Node&gt; stack = new Stack&lt;&gt;();
stack.add(root);
while (!stack.isEmpty()) {
 Node node = stack.pop();
 System.out.print(node.getData() + &quot; &quot;);

 Node right = node.getRight();
 if (right != null) {
 stack.push(right);
 }

 Node left = node.getLeft();
 if (left != null) {
 stack.push(left);
 }
}
</code></pre>

I am looking for a non-recursive depth first search algorithm for a non-binary tree. Any help is very much appreciated.

Non-recursive depth first search algorithm

Java

我正在寻找一种非递归深度优先搜索算法，用于非二叉树。任何帮助都是非常感谢的。

问非递归深度优先搜索算法
EN

回答 13

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问非递归深度优先搜索算法EN

回答 13

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问非递归深度优先搜索算法
EN