递归执行广度优先搜索

小开

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

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


BFS(Q)
}

小开

如果使用数组来支持二叉树，则可以用代数方法确定下一个节点。如果i是一个节点，那么它的子节点可以在2i + 1(左边的节点)和2i + 2(右边的节点)找到。节点的下一个邻居由i + 1给出，除非i是2的幂

下面是在数组支持的二叉搜索树上实现宽度优先搜索的伪代码。这假设一个固定大小的数组，因此一个固定深度的树。它将查看无父节点，并可能创建难以管理的大堆栈。

bintree-bfs(bintree, elt, i)
if (i == LENGTH)
return false


else if (bintree[i] == elt)
return true


else
return bintree-bfs(bintree, elt, i+1)

小开

愚蠢的方式:

template<typename T>
struct Node { Node* left; Node* right; T value; };


template<typename T, typename P>
bool searchNodeDepth(Node<T>* node, Node<T>** result, int depth, P pred) {
if (!node) return false;
if (!depth) {
if (pred(node->value)) {
*result = node;
}
return true;
}
--depth;
searchNodeDepth(node->left, result, depth, pred);
if (!*result)
searchNodeDepth(node->right, result, depth, pred);
return true;
}


template<typename T, typename P>
Node<T>* searchNode(Node<T>* node, P pred) {
Node<T>* result = NULL;
int depth = 0;
while (searchNodeDepth(node, &result, depth, pred) && !result)
++depth;
return result;
}


int main()
{
// a c   f
//  b   e
//    d
Node<char*>
a = { NULL, NULL, "A" },
c = { NULL, NULL, "C" },
b = { &a, &c, "B" },
f = { NULL, NULL, "F" },
e = { NULL, &f, "E" },
d = { &b, &e, "D" };


Node<char*>* found = searchNode(&d, [](char* value) -> bool {
printf("%s\n", value);
return !strcmp((char*)value, "F");
});


printf("found: %s\n", found->value);


return 0;
}

小开

最佳答案

(我假设这只是某种思维练习，或者甚至是一个恶作剧的家庭作业/面试问题，但是我想我可以想象一些奇怪的场景，由于某种原因不允许有任何堆空间[一些非常糟糕的自定义内存管理器?一些奇怪的运行时/操作系统问题?当你仍然可以访问堆栈时…)

宽度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎是相反的，因此试图使用调用堆栈(这是一个堆栈，因此得名)作为辅助存储(队列)几乎是注定要失败的，除非您对调用堆栈做了一些不应该做的愚蠢可笑的事情。

同样，您尝试实现的任何非尾递归本质上都是向算法添加堆栈。这使得它不再在二叉树上进行广度优先搜索，因此传统BFS的运行时和诸如此类的东西不再完全适用。当然，您总是可以简单地将任何循环转换为递归调用，但这并不是任何有意义的递归。

然而，正如其他人所演示的那样，有一些方法可以以一定的代价实现一些遵循BFS语义的东西。如果比较的成本很高，但节点遍历的成本很低，那么就像@Simon巴肯所做的那样，你可以简单地运行迭代深度优先搜索，只处理叶子。这意味着堆中没有存储增长的队列，只有一个局部深度变量，并且当树被一遍又一遍地遍历时，堆栈将在调用堆栈上反复构建。正如@Patrick指出的那样，数组支持的二叉树通常以宽度优先遍历顺序存储，因此对其进行宽度优先搜索是微不足道的，也不需要辅助队列。

小开

我必须实现以BFS顺序输出的堆遍历。它实际上不是BFS，但完成了相同的任务。

private void getNodeValue(Node node, int index, int[] array) {
array[index] = node.value;
index = (index*2)+1;


Node left = node.leftNode;
if (left!=null) getNodeValue(left,index,array);
Node right = node.rightNode;
if (right!=null) getNodeValue(right,index+1,array);
}


public int[] getHeap() {
int[] nodes = new int[size];
getNodeValue(root,0,nodes);
return nodes;
}

小开

下面的方法使用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;
}
}

小开

#include <bits/stdc++.h>
using namespace std;
#define Max 1000


vector <int> adj[Max];
bool visited[Max];


void bfs_recursion_utils(queue<int>& Q) {
while(!Q.empty()) {
int u = Q.front();
visited[u] = true;
cout << u << endl;
Q.pop();
for(int i = 0; i < (int)adj[u].size(); ++i) {
int v = adj[u][i];
if(!visited[v])
Q.push(v), visited[v] = true;
}
bfs_recursion_utils(Q);
}
}


void bfs_recursion(int source, queue <int>& Q) {
memset(visited, false, sizeof visited);
Q.push(source);
bfs_recursion_utils(Q);
}


int main(void) {
queue <int> Q;
adj[1].push_back(2);
adj[1].push_back(3);
adj[1].push_back(4);


adj[2].push_back(5);
adj[2].push_back(6);


adj[3].push_back(7);


bfs_recursion(1, Q);
return 0;
}

小开

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

小开

下面是一个python实现:

graph = {'A': ['B', 'C'],
'B': ['C', 'D'],
'C': ['D'],
'D': ['C'],
'E': ['F'],
'F': ['C']}


def bfs(paths, goal):
if not paths:
raise StopIteration


new_paths = []
for path in paths:
if path[-1] == goal:
yield path


last = path[-1]
for neighbor in graph[last]:
if neighbor not in path:
new_paths.append(path + [neighbor])
yield from bfs(new_paths, goal)




for path in bfs([['A']], 'D'):
print(path)

小开

我发现了一个非常漂亮的递归(甚至函数)宽度优先遍历相关算法。不是我的想法，但我认为在这个话题中应该提到它。

Chris Okasaki用3张图片非常清楚地解释了他在ICFP 2000上http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html的宽度优先编号算法。

Debasish Ghosh的Scala实现，我在http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html找到的，是:

trait Tree[+T]
case class Node[+T](data: T, left: Tree[T], right: Tree[T]) extends Tree[T]
case object E extends Tree[Nothing]


def bfsNumForest[T](i: Int, trees: Queue[Tree[T]]): Queue[Tree[Int]] = {
if (trees.isEmpty) Queue.Empty
else {
trees.dequeue match {
case (E, ts) =>
bfsNumForest(i, ts).enqueue[Tree[Int]](E)
case (Node(d, l, r), ts) =>
val q = ts.enqueue(l, r)
val qq = bfsNumForest(i+1, q)
val (bb, qqq) = qq.dequeue
val (aa, tss) = qqq.dequeue
tss.enqueue[org.dg.collection.BFSNumber.Tree[Int]](Node(i, aa, bb))
}
}
}


def bfsNumTree[T](t: Tree[T]): Tree[Int] = {
val q = Queue.Empty.enqueue[Tree[T]](t)
val qq = bfsNumForest(1, q)
qq.dequeue._1
}

小开

下面是递归BFS的Scala 2.11.4实现。为了简洁起见，我牺牲了尾部调用优化，但是TCOd版本非常相似。另见@snv的帖子。

import scala.collection.immutable.Queue


object RecursiveBfs {
def bfs[A](tree: Tree[A], target: A): Boolean = {
bfs(Queue(tree), target)
}


private def bfs[A](forest: Queue[Tree[A]], target: A): Boolean = {
forest.dequeueOption exists {
case (E, tail) => bfs(tail, target)
case (Node(value, _, _), _) if value == target => true
case (Node(_, l, r), tail) => bfs(tail.enqueue(List(l, r)), target)
}
}


sealed trait Tree[+A]
case class Node[+A](data: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case object E extends Tree[Nothing]
}

小开

下面是一个JavaScript实现，它用深度优先递归来伪造广度优先遍历。我将每个深度的节点值存储在一个数组中，在一个散列中。如果一个级别已经存在(我们有一个碰撞)，那么我们只是推到该级别的数组。你也可以使用数组而不是JavaScript对象，因为我们的关卡是数值的，可以作为数组下标。您可以返回节点、值、转换为链表或任何您想要的内容。为了简单起见，我只是返回值。

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

小开

Java中简单的BFS和DFS递归:
只需要在堆栈/队列中推送/提供树的根节点并调用这些函数

public static void breadthFirstSearch(Queue queue) {


if (queue.isEmpty())
return;


Node node = (Node) queue.poll();


System.out.println(node + " ");


if (node.right != null)
queue.offer(node.right);


if (node.left != null)
queue.offer(node.left);


breadthFirstSearch(queue);
}


public static void depthFirstSearch(Stack stack) {


if (stack.isEmpty())
return;


Node node = (Node) stack.pop();


System.out.println(node + " ");


if (node.right != null)
stack.push(node.right);


if (node.left != null)
stack.push(node.left);


depthFirstSearch(stack);
}

小开

下面使用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])

小开

以下是我的完全递归实现的双向图的广度优先搜索的代码，而不使用循环和队列。




public class Graph
{
public int V;
public LinkedList<Integer> adj[];


Graph(int v)
{
V = v;
adj = new LinkedList[v];
for (int i=0; i<v; ++i)
adj[i] = new LinkedList<>();
}


void addEdge(int v,int w)
{
adj[v].add(w);
adj[w].add(v);
}


public LinkedList<Integer> getAdjVerted(int vertex)
{
return adj[vertex];
}


public String toString()
{
String s = "";


for (int i=0;i<adj.length;i++)
{
s = s +"\n"+i +"-->"+ adj[i] ;
}
return s;
}
}


//BFS IMPLEMENTATION


public static void recursiveBFS(Graph graph, int vertex,boolean visited[], boolean isAdjPrinted[])
{
if (!visited[vertex])
{
System.out.print(vertex +" ");
visited[vertex] = true;
}


if(!isAdjPrinted[vertex])
{
isAdjPrinted[vertex] = true;
List<Integer> adjList = graph.getAdjVerted(vertex);
printAdjecent(graph, adjList, visited, 0,isAdjPrinted);
}
}


public static void recursiveBFS(Graph graph, List<Integer> vertexList, boolean visited[], int i, boolean isAdjPrinted[])
{
if (i < vertexList.size())
{
recursiveBFS(graph, vertexList.get(i), visited, isAdjPrinted);
recursiveBFS(graph, vertexList, visited, i+1, isAdjPrinted);
}
}


public static void printAdjecent(Graph graph, List<Integer> list, boolean visited[], int i, boolean isAdjPrinted[])
{
if (i < list.size())
{
if (!visited[list.get(i)])
{
System.out.print(list.get(i)+" ");
visited[list.get(i)] = true;
}
printAdjecent(graph, list, visited, i+1, isAdjPrinted);
}
else
{
recursiveBFS(graph, list, visited, 0, isAdjPrinted);
}
}

小开

二进制(或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));
}

小开

下面是简短的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)

小开

下面是一个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 = []

小开

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

首先，@Tanzelax的回答是:

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

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

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

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

这里的直觉是:

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

小开

c#实现的递归宽度优先搜索二叉树算法。

二叉树数据可视化 .

IDictionary<string, string[]> graph = new Dictionary<string, string[]> {
{"A", new [] {"B", "C"}},
{"B", new [] {"D", "E"}},
{"C", new [] {"F", "G"}},
{"E", new [] {"H"}}
};


void Main()
{
var pathFound = BreadthFirstSearch("A", "H", new string[0]);
Console.WriteLine(pathFound); // [A, B, E, H]


var pathNotFound = BreadthFirstSearch("A", "Z", new string[0]);
Console.WriteLine(pathNotFound); // []
}


IEnumerable<string> BreadthFirstSearch(string start, string end, IEnumerable<string> path)
{
if (start == end)
{
return path.Concat(new[] { end });
}


if (!graph.ContainsKey(start)) { return new string[0]; }


return graph[start].SelectMany(letter => BreadthFirstSearch(letter, end, path.Concat(new[] { start })));
}

如果你想让算法不仅适用于二叉树，而且适用于有两个或两个以上节点指向同一个节点的图，你必须通过持有已经访问过的节点列表来避免自循环。实现可能是这样的。

图形数据可视化 .

IDictionary<string, string[]> graph = new Dictionary<string, string[]> {
{"A", new [] {"B", "C"}},
{"B", new [] {"D", "E"}},
{"C", new [] {"F", "G", "E"}},
{"E", new [] {"H"}}
};


void Main()
{
var pathFound = BreadthFirstSearch("A", "H", new string[0], new List<string>());
Console.WriteLine(pathFound); // [A, B, E, H]


var pathNotFound = BreadthFirstSearch("A", "Z", new string[0], new List<string>());
Console.WriteLine(pathNotFound); // []
}


IEnumerable<string> BreadthFirstSearch(string start, string end, IEnumerable<string> path, IList<string> visited)
{
if (start == end)
{
return path.Concat(new[] { end });
}


if (!graph.ContainsKey(start)) { return new string[0]; }




return graph[start].Aggregate(new string[0], (acc, letter) =>
{
if (visited.Contains(letter))
{
return acc;
}


visited.Add(letter);


var result = BreadthFirstSearch(letter, end, path.Concat(new[] { start }), visited);
return acc.Concat(result).ToArray();
});
}

小开

我已经用c++做了一个程序，它是在联合和不联合图工作。

    #include <queue>
#include "iostream"
#include "vector"
#include "queue"


using namespace std;


struct Edge {
int source,destination;
};


class Graph{
int V;
vector<vector<int>> adjList;
public:


Graph(vector<Edge> edges,int V){
this->V = V;
adjList.resize(V);
for(auto i : edges){
adjList[i.source].push_back(i.destination);
//     adjList[i.destination].push_back(i.source);
}
}
void BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q);
void BFSRecursivelyJointandDisjointGraph(int s);
void printGraph();




};


void Graph :: printGraph()
{
for (int i = 0; i < this->adjList.size(); i++)
{
cout << i << " -- ";
for (int v : this->adjList[i])
cout <<"->"<< v << " ";
cout << endl;
}
}




void Graph ::BFSRecursivelyJoinandDisjointtGraphUtil(vector<bool> &discovered, queue<int> &q) {
if (q.empty())
return;
int v = q.front();
q.pop();
cout << v <<" ";
for (int u : this->adjList[v])
{
if (!discovered[u])
{
discovered[u] = true;
q.push(u);
}
}
BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);


}


void Graph ::BFSRecursivelyJointandDisjointGraph(int s) {
vector<bool> discovered(V, false);
queue<int> q;


for (int i = s; i < V; i++) {
if (discovered[i] == false)
{
discovered[i] = true;
q.push(i);
BFSRecursivelyJoinandDisjointtGraphUtil(discovered, q);
}
}
}


int main()
{


vector<Edge> edges =
{
{0, 1}, {0, 2}, {1, 2}, {2, 0}, {2,3},{3,3}
};


int V = 4;
Graph graph(edges, V);
//   graph.printGraph();
graph.BFSRecursivelyJointandDisjointGraph(2);
cout << "\n";








edges = {
{0,4},{1,2},{1,3},{1,4},{2,3},{3,4}
};


Graph graph2(edges,5);


graph2.BFSRecursivelyJointandDisjointGraph(0);
return 0;
}

小开

我认为这可以使用指针不使用任何队列来完成。

基本上我们在任何地方都维护两个指针，一个指向父结点，另一个指向待处理的子结点(链接列表指向所有已处理的子结点)

现在你只需将子对象的指针&当父级处理完成时，你只需让子级成为下一级处理的父级

以下是我的代码:

//Tree Node
struct Node {
int val;
Node* left;
Node* right;
Node* next;


Node() : val(0), left(NULL), right(NULL), next(NULL) {}


Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}


Node(int _val, Node* _left, Node* _right, Node* _next)
: val(_val), left(_left), right(_right), next(_next) {}
};

/ / Algorightm:

    void LevelTraverse(Node* parent,Node* chidstart,Node* childend ){
if(!parent && !chidstart) return;  // we processed everything
        

if(!parent && chidstart){ //finished processing last level
parent=chidstart;chidstart=childend=NULL; // assgin child to parent for processing next level
LevelTraverse(parent,chidstart,childend);
}else if(parent && !chidstart){ // This is new level first node tobe processed
Node* temp=parent; parent=parent->next;
if(temp->left) { childend=chidstart=temp->left; }
if(chidstart){
if(temp->right) { childend->next=temp->right; childend=temp->right; }
}else{
if(temp->right) { childend=chidstart=temp->right; }
}
LevelTraverse(parent,chidstart,childend);
}else if(parent && chidstart){ //we are in mid of some level processing
Node* temp=parent; parent=parent->next;
if(temp->left) { childend->next=temp->left; childend=temp->left; }
if(temp->right) { childend->next=temp->right; childend=temp->right; }
LevelTraverse(parent,chidstart,childend);
}
}

//驱动代码:

    Node* connect(Node* root) {
if(!root) return NULL;
Node* parent; Node* childs, *childe; parent=childs=childe=NULL;
parent=root;
LevelTraverse(parent, childs, childe);
return root;
}

小开

在研究AlgoExpert时，从这个问题的改编。下面的Class已经在提示符中提供了。这里是python中的迭代和递归解决方案。这个问题的目标是返回一个输出array，其中列出了按访问顺序排列的节点名称。如果遍历的顺序是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