我正在寻找一个非二叉树的非递归深度优先搜索算法。任何帮助都非常感激。
当前回答
基于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); } }
其他回答
使用堆栈来跟踪节点
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)
}
如果你有指向父节点的指针,你可以在没有额外内存的情况下完成。
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
使用ES6生成器的非递归DFS
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
}
}
它与典型的非递归DFS不同,可以很容易地检测给定节点的所有可达后代何时被处理,并维护列表/堆栈中的当前路径。
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
}
两者的对称相当酷。
更新:如前所述,take_first()删除并返回列表中的第一个元素。
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()
}