下面使用Haskell对我来说似乎很自然。在树的各个层次上递归迭代(这里我将名字收集到一个大的有序字符串中，以显示树的路径):

data Node = Node {name :: String, children :: [Node]}
aTree = Node "r" [Node "c1" [Node "gc1" [Node "ggc1" []], Node "gc2" []] , Node "c2" [Node "gc3" []], Node "c3" [] ]
breadthFirstOrder x = levelRecurser [x]
    where levelRecurser level = if length level == 0
                                then ""
                                else concat [name node ++ " " | node <- level] ++ levelRecurser (concat [children node | node <- level])

在学习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

我找不到一种完全递归的方法(没有任何辅助数据结构)。但是如果队列Q是通过引用传递的，那么你可以得到下面这个愚蠢的尾部递归函数:

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

下面的方法使用DFS算法来获取特定深度的所有节点——这与对该级别进行BFS相同。如果您找到树的深度，并对所有级别执行此操作，结果将与BFS相同。

public void PrintLevelNodes(Tree root, int level) {
    if (root != null) {
        if (level == 0) {
            Console.Write(root.Data);
            return;
        }
        PrintLevelNodes(root.Left, level - 1);
        PrintLevelNodes(root.Right, level - 1);
    }
}

for (int i = 0; i < depth; i++) {
    PrintLevelNodes(root, i);
}

找到树的深度是小菜一碟:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}

下面是简短的Scala解决方案:

  def bfs(nodes: List[Node]): List[Node] = {
    if (nodes.nonEmpty) {
      nodes ++ bfs(nodes.flatMap(_.children))
    } else {
      List.empty
    }
  }

使用返回值作为累加器的想法是很适合的。 可以在其他语言中以类似的方式实现，只需确保您的递归函数处理的节点列表。

测试代码清单(使用@marco测试树):

import org.scalatest.FlatSpec

import scala.collection.mutable

class Node(val value: Int) {

  private val _children: mutable.ArrayBuffer[Node] = mutable.ArrayBuffer.empty

  def add(child: Node): Unit = _children += child

  def children = _children.toList

  override def toString: String = s"$value"
}

class BfsTestScala extends FlatSpec {

  //            1
  //          / | \
  //        2   3   4
  //      / |       | \
  //    5   6       7  8
  //  / |           | \
  // 9  10         11  12
  def tree(): Node = {
    val root = new Node(1)
    root.add(new Node(2))
    root.add(new Node(3))
    root.add(new Node(4))
    root.children(0).add(new Node(5))
    root.children(0).add(new Node(6))
    root.children(2).add(new Node(7))
    root.children(2).add(new Node(8))
    root.children(0).children(0).add(new Node(9))
    root.children(0).children(0).add(new Node(10))
    root.children(2).children(0).add(new Node(11))
    root.children(2).children(0).add(new Node(12))
    root
  }

  def bfs(nodes: List[Node]): List[Node] = {
    if (nodes.nonEmpty) {
      nodes ++ bfs(nodes.flatMap(_.children))
    } else {
      List.empty
    }
  }

  "BFS" should "work" in {
    println(bfs(List(tree())))
  }
}

输出:

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

设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)