跟蹤深度非遞歸廣度優先搜索

Question

我有以下算法的廣度優先搜索：

q := [] 
q.append(root node of tree) 
while q: 
    n := q.pop(0) 
    yield n 
     if n has children: 
      c := children of node 
      for i in c: 
       q.append(i) 

1）這怎麼可能延長，因此跟蹤當前的深度？ 2）將在這一擴展應用到類似的算法對於深度優先搜索，與由堆代替隊列q？

Answer 1

只是存儲與節點的深度和每次生成一個節點的子節點的時間增加了。

q := [(root, 0)] 
while q: 
    n, depth := q.pop() 
    yield n, depth 
    if n has children: 
     c := children of n 
     for i in c: 
      q.append(i, depth + 1) 

這個想法擴展到DFS和啓發式引導搜索。

Answer 2

要擴大larsmans'優秀的答案，下面是我的深度限制的廣度優先二叉樹的遍歷c++代碼。

（代碼假設節點不包括深度信息，並進行排隊之前包裹在NodeAndDepth結構的每個節點。）

struct NodeAndDepth { 
    NodeAndDepth(Node *n, unsigned int d) : node(n), depth(d) {} 
    Node *node; 
    unsigned int depth; 
}; 

void traverseBreadthFirst_WithDepthLimit(Node *root, unsigned int maxDepth) { 
    if (maxDepth == 0 || root == NULL) { return; } 

    std::queue<NodeAndDepth> q; 
    q.push(NodeAndDepth(root, 1)); 

    while (!q.empty()) { 
     NodeAndDepth n = q.front(); q.pop(); 

     // visit(n.node); 
     // cout << n.depth << ": " << n.node->payload << endl; 

     if (n.depth >= maxDepth) { continue; } 

     if (n.node->left != NULL) { 
      q.push(NodeAndDepth(n.node->left, n.depth + 1)); 
     } 

     if (n.node->right != NULL) { 
      q.push(NodeAndDepth(n.node->right, n.depth + 1)); 
     } 
    } 
}