stack.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile
1
如果您有指向父节点的指针,则可以在没有额外内存的情况下执行此操作 .
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
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)
}
1
虽然"use a stack"可以作为人为的面试问题的答案,但实际上,它只是明确地做了一个递归程序在幕后做的事情 .
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);
}
}
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;
}
28
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);
}
}
0
基于@ biziclop答案的伪代码:
仅使用基本结构:变量,数组,if,while和for
函数 getNode(id) 和 getChildren(id)
假设已知节点数 N
注意:我使用的是1的数组索引,而不是0 .
广度优先
S = Array(N)
S[1] = 1; // root id
cur = 1;
last = 1
while cur <= last
id = S[cur]
node = getNode(id)
children = getChildren(id)
n = length(children)
for i = 1..n
S[ last+i ] = children[i]
end
last = last+n
cur = cur+1
visit(node)
end
深度优先
S = Array(N)
S[1] = 1; // root id
cur = 1;
while cur > 0
id = S[cur]
node = getNode(id)
children = getChildren(id)
n = length(children)
for i = 1..n
// assuming children are given left-to-right
S[ cur+i-1 ] = children[ n-i+1 ]
// otherwise
// S[ cur+i-1 ] = children[i]
end
cur = cur+n-1
visit(node)
end
0
完整的示例工作代码,没有堆栈:
import java.util.*;
class Graph {
private List<List<Integer>> adj;
Graph(int numOfVertices) {
this.adj = new ArrayList<>();
for (int i = 0; i < numOfVertices; ++i)
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++);// 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++);// 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);
}}
16 回答
DFS:
BFS:
两者的对称非常酷 .
Update: 正如所指出的,
take_first()
删除并返回列表中的第一个元素 .您将使用stack来保存尚未访问过的节点:
如果您有指向父节点的指针,则可以在没有额外内存的情况下执行此操作 .
请注意,如果子节点存储为数组而不是通过兄弟指针存储,则可以将下一个兄弟节点存储为:
使用堆栈跟踪节点
虽然"use a stack"可以作为人为的面试问题的答案,但实际上,它只是明确地做了一个递归程序在幕后做的事情 .
递归使用程序内置堆栈 . 当你调用一个函数时,它会将函数的参数推送到堆栈上,当函数返回时,它会弹出程序堆栈 .
基于biziclops的ES6实现很棒的答案:
一般逻辑是,将节点(从根开始)推入Stack,Pop()和Print()值 . 然后,如果它有子(左和右)将它们推入堆栈 - 首先向右推,这样您将首先访问左子(在访问节点本身之后) . 当stack为空()时,您将访问预订中的所有节点 .
假设您要在访问图表中的每个节点时执行通知 . 简单的递归实现是:
好的,现在你想要一个基于堆栈的实现,因为你的例子不起作用 . 例如,复杂的图形可能会导致程序堆栈崩溃,您需要实现非递归版本 . 最大的问题是知道何时发出通知 .
以下伪代码可以工作(Java和C的混合可读性):
它看起来很复杂,但发布通知所需的额外逻辑是因为你需要以相反的顺序通知--DFS从root开始但最后通知它,这与BFS非常简单,实现起来很简单 .
对于踢,请尝试以下图:节点是s,t,v和w . 有向边是:s-> t,s-> v,t-> w,v-> w,和v-> t . 运行您自己的DFS实现,并且应该访问节点的顺序必须是:w,t,v,s DFS的笨拙实现可能首先通知t,这表示存在错误 . DFS的递归实现总是最后到达 .
使用ES6生成器的非递归DFS
它偏离typical non-recursive DFS以轻松检测给定节点的所有可到达后代何时被处理并维护列表/堆栈中的当前路径 .
你可以使用堆栈 . 我使用Adjacency Matrix实现了图形:
Java中的DFS迭代:
http://www.youtube.com/watch?v=zLZhSSXAwxI
刚刚观看了这段视频并推出了实施方案 . 我很容易理解 . 请批评这个 .
使用
Stack
,以下是要遵循的步骤:然后按下堆栈上的第一个顶点,如果可能,访问相邻的未访问顶点,对其进行标记,然后将其推入堆栈 .
如果你不能按照步骤1,那么,如果可能的话,从堆栈中弹出一个顶点 .
如果您无法执行步骤1或步骤2,那么您就完成了 .
这是遵循以上步骤的Java程序:
基于@ biziclop答案的伪代码:
仅使用基本结构:变量,数组,if,while和for
函数
getNode(id)
和getChildren(id)
假设已知节点数
N
广度优先
深度优先
完整的示例工作代码,没有堆栈:
输出:广度优先遍历 - 从顶点2开始:2 0 3 1 4深度优先遍历 - 从顶点2开始:2 3 4 1 0