在学习AlgoExpert时，对这个问题进行了改编。提示符中已经提供了以下Class。这里是python中的迭代和递归解决方案。这个问题的目标是返回一个输出数组，其中列出了按访问顺序排列的节点名称。如果遍历顺序为A -> B -> D -> F，则输出为['A'，'B'，'D'，'F']

class Node:
    def __init__(self, name):
        self.children = []
        self.name = name

    def addChild(self, name):
        self.children.append(Node(name))
        return self

递归

def breadthFirstSearch(self, array):
    return self._bfs(array, [self])
    
def _bfs(self, array, visited):

    # Base case - no more nodes to visit
    if len(visited) == 0:
        return array

    node = visited.pop(0)
    array.append(node.name)
    visited.extend(node.children)
    return self._bfs(array, visited)

迭代

def breadthFirstSearch(self, array):
    array.append(self.name)
    queue = [self]
    while len(queue) > 0:
        node = queue.pop(0)
        for child in node.children:
            array.append(child.name)
            queue.append(child)
    return array

设v为起始顶点

设G是问题中的图

下面是不使用队列的伪代码

Initially label v as visited as you start from v
BFS(G,v)
    for all adjacent vertices w of v in G:
        if vertex w is not visited:
            label w as visited
    for all adjacent vertices w of v in G:
        recursively call BFS(G,w)

Here is a JavaScript Implementation that fakes Breadth First Traversal with Depth First recursion. I'm storing the node values at each depth inside an array, inside of a hash. If a level already exists(we have a collision), so we just push to the array at that level. You could use an array instead of a JavaScript object as well since our levels are numeric and can serve as array indices. You can return nodes, values, convert to a Linked List, or whatever you want. I'm just returning values for the sake of simplicity.

BinarySearchTree.prototype.breadthFirstRec = function() {

    var levels = {};

    var traverse = function(current, depth) {
        if (!current) return null;
        if (!levels[depth]) levels[depth] = [current.value];
        else levels[depth].push(current.value);
        traverse(current.left, depth + 1);
        traverse(current.right, depth + 1);
    };

    traverse(this.root, 0);
    return levels;
};


var bst = new BinarySearchTree();
bst.add(20, 22, 8, 4, 12, 10, 14, 24);
console.log('Recursive Breadth First: ', bst.breadthFirstRec());
/*Recursive Breadth First:  
{ '0': [ 20 ],
  '1': [ 8, 22 ],
  '2': [ 4, 12, 24 ],
  '3': [ 10, 14 ] } */

下面是一个使用迭代方法的实际广度优先遍历的示例。

BinarySearchTree.prototype.breadthFirst = function() {

    var result = '',
        queue = [],
        current = this.root;

    if (!current) return null;
    queue.push(current);

    while (current = queue.shift()) {
        result += current.value + ' ';
        current.left && queue.push(current.left);
        current.right && queue.push(current.right);
    }
    return result;
};

console.log('Breadth First: ', bst.breadthFirst());
//Breadth First:  20 8 22 4 12 24 10 14

下面是一个BFS递归遍历Python实现，用于没有周期的图。

def bfs_recursive(level):
    '''
     @params level: List<Node> containing the node for a specific level.
    '''
    next_level = []
    for node in level:
        print(node.value)
        for child_node in node.adjency_list:
            next_level.append(child_node)
    if len(next_level) != 0:
        bfs_recursive(next_level)


class Node:
    def __init__(self, value):
        self.value = value
        self.adjency_list = []

二进制(或n-ary)树的BFS可以在没有队列的情况下递归完成，如下所示(在Java中):

public class BreathFirst {

    static class Node {
        Node(int value) {
            this(value, 0);
        }
        Node(int value, int nChildren) {
            this.value = value;
            this.children = new Node[nChildren];
        }
        int value;
        Node[] children;
    }

    static void breathFirst(Node root, Consumer<? super Node> printer) {
        boolean keepGoing = true;
        for (int level = 0; keepGoing; level++) {
            keepGoing = breathFirst(root, printer, level);
        }
    }

    static boolean breathFirst(Node node, Consumer<? super Node> printer, int depth) {
        if (depth < 0 || node == null) return false;
        if (depth == 0) {
            printer.accept(node);
            return true;
        }
        boolean any = false;
        for (final Node child : node.children) {
            any |= breathFirst(child, printer, depth - 1);
        }
        return any;
    }
}

按升序遍历打印数字1-12的示例:

public static void main(String... args) {
    //            1
    //          / | \
    //        2   3   4
    //      / |       | \
    //    5   6       7  8
    //  / |           | \
    // 9  10         11  12

    Node root = new Node(1, 3);
    root.children[0] = new Node(2, 2);
    root.children[1] = new Node(3);
    root.children[2] = new Node(4, 2);
    root.children[0].children[0] = new Node(5, 2);
    root.children[0].children[1] = new Node(6);
    root.children[2].children[0] = new Node(7, 2);
    root.children[2].children[1] = new Node(8);
    root.children[0].children[0].children[0] = new Node(9);
    root.children[0].children[0].children[1] = new Node(10);
    root.children[2].children[0].children[0] = new Node(11);
    root.children[2].children[0].children[1] = new Node(12);

    breathFirst(root, n -> System.out.println(n.value));
}

我想在上面的答案中加上我的观点，如果语言支持生成器之类的东西，bfs可以协递归地完成。

首先，@Tanzelax的回答是:

宽度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎是相反的，因此试图使用调用堆栈(因此得名为堆栈)作为辅助存储(队列)几乎是注定要失败的

实际上，普通函数调用的堆栈不会像普通堆栈那样运行。但是生成器函数将暂停函数的执行，因此它给了我们产生下一层节点的子节点的机会，而无需深入研究节点的更深层次的后代。

下面的代码是Python中的递归bfs。

def bfs(root):
  yield root
  for n in bfs(root):
    for c in n.children:
      yield c

这里的直觉是:

BFS首先将根作为第一个结果返回 假设我们已经有了BFS序列，BFS中的下一层元素是序列中前一个节点的直接子节点 重复以上两个步骤