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

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

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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