我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
基于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); } }
其他回答
虽然“使用堆栈”可能是人为的面试问题的答案,但实际上,它只是显式地做递归程序在幕后所做的事情。
递归使用程序内置堆栈。当你调用一个函数时,它将函数的参数推入堆栈,当函数返回时,它通过弹出程序堆栈来执行。
http://www.youtube.com/watch?v=zLZhSSXAwxI
刚刚看了这个视频,并提出了实施方案。这对我来说似乎很容易理解。请评论一下。
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步,那么,如果可能的话,弹出一个顶点 堆栈。 如果你不能遵循第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;
}
如果你有指向父节点的指针,你可以在没有额外内存的情况下完成。
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.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile