递归执行广度优先搜索

Question

假设您想要递归地实现二叉树的广度优先搜索。你会怎样做呢？

是否可以仅使用调用堆栈作为辅助存储？

Answer 1

（我假设这只是某种思维练习，甚至是一个技巧作业/面试问题，但我想我可以想象一些奇怪的场景，由于某种原因你不允许任何堆空间[一些非常糟糕的习惯]内存管理器？一些奇怪的运行时/操作系统问题？]而您仍然可以访问堆栈...）

广度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎相反，因此尝试使用调用堆栈（这是一个堆栈，因此得名）作为辅助存储（队列）几乎注定会失败，除非您正在这样做调用堆栈中的一些愚蠢可笑的事情是你不应该做的。

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

然而，正如其他人所演示的，有一些方法可以以一定的成本实现遵循 BFS 语义的东西。如果比较的成本很昂贵但节点遍历很便宜，则如 @Simon Buchan 做到了，您可以简单地运行迭代深度优先搜索，仅处理叶子。这意味着堆中没有存储增长的队列，只是一个本地深度变量，并且随着树被一遍又一遍地遍历，堆栈在调用堆栈上一遍又一遍地构建。正如 @Patrick 指出的，由数组支持的二叉树是无论如何，通常以广度优先遍历顺序存储，因此对其进行广度优先搜索将是微不足道的，也不需要辅助队列。

Answer 2

如果使用数组来支持二叉树，则可以通过代数方式确定下一个节点。如果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)        

Answer 3

我找不到完全递归的方法（没有任何辅助数据结构）。但是如果队列 Q 是通过引用传递的，那么您可以拥有以下傻尾递归函数：

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

     BFS(Q)
}

Answer 4

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

Answer 5

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);
}

Answer 6

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

Answer 7

我想将我的美分添加到最佳答案中，因为如果语言支持诸如生成器之类的东西，则可以通过以下方式完成bfs： -递归地。

首先，@Tanzelax 的回答是：

广度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎相反，因此尝试使用调用堆栈（这是一个堆栈，因此得名）作为辅助存储（队列）几乎注定会失败

事实上，普通函数调用的堆栈不会表现得像一个普通的堆栈。但是生成器函数将暂停函数的执行，因此它使我们有机会生成下一级节点的子节点，而无需深入研究该节点的更深层次的后代。

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

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

这里的直觉是：

1. bfs 首先将返回根作为第一个结果
2. 假设我们已经有了 bfs 序列，bfs 中的下一级元素是序列中前一个节点的直接子节点
3. 重复上述两个过程

Answer 8

我发现了一个非常漂亮的递归（甚至是函数式）广度优先遍历相关算法。不是我的想法，但我认为应该在本主题中提及。

Chris Okasaki 在 ICFP 2000 中解释了他的广度优先编号算法，网址为 http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html非常清楚，只有3张图片。

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
}

Answer 9

笨办法：

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;
}

Answer 10

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

Answer 11

这是一个 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)

Answer 12

这是递归 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]
}

Answer 13

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

Answer 14

我必须实现以 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;
}

Answer 15

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

Answer 16

二叉（或 n 叉）树的 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));
}

Answer 17

来自在 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

Answer 18

除了最佳答案中的精彩解释之外，我还会添加另一个可能的解决方案没有队列 。它使用递归和生成器：

class TreeNode {
    constructor(
        public readonly value: number,
        public readonly children: TreeNode[] = [],
    ) {
    }
}

function* bfs(rootNode: TreeNode, recursionLevel: number = 0): Generator<TreeNode> {
    yield rootNode

    if (recursionLevel > 10) return;    // Stop excessive recursion using hard limit
    for (const node of bfs(rootNode, recursionLevel + 1)) {
        for (const child of node.children) {
            yield child
        }
    }
}

注意：出于演示目的，无论树深度如何，它始终进行 10 次递归调用。对于更高级的版本，请参见下文。

测试脚本：

const tree = new TreeNode(1, [
    new TreeNode(11, [
        new TreeNode(111),
        new TreeNode(112),
        new TreeNode(113, [
            new TreeNode(1131),
        ]),
    ]),
    new TreeNode(12, [
        new TreeNode(121),
        new TreeNode(122, [
            new TreeNode(1221),
        ]),
    ]),
    new TreeNode(13, [
        new TreeNode(131),
    ]),
]);

for (const node of bfs(tree)) {
    console.log(node.value);
}

输出：

1
11
12
13
111
112
113
121
122
131
1131
1221

更高级的版本涉及根据访问的级别停止递归。例如：

let maxWalkLevel = 0;

function* bfs(rootNode: TreeNode, recursionLevel: number = 0): Generator<[number, TreeNode]> {
    yield [0, rootNode];

    if (recursionLevel > maxWalkLevel) return;   // Stop excessive recursion

    for (const [walkLevel, node] of bfs(rootNode, recursionLevel + 1)) {
        for (const child of node.children) {
            maxWalkLevel = Math.max(maxWalkLevel, walkLevel + 1);
            yield [walkLevel + 1, child]
        }
    }
}

输出：

0 - 1
1 - 11
1 - 12
1 - 13
2 - 111
2 - 112
2 - 113
2 - 121
2 - 122
2 - 131
3 - 1131
3 - 1221

Answer 19

#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;
}

Answer 20

这是一个 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

Answer 21

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

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);
        }
    }

Answer 22

二叉树递归广度优先搜索算法的 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();
    });
}

Answer 23

我用 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;
}

Answer 24

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

基本上我们在任何一点都维护两个指针，一个指向父级，另一个指向要处理的子级（链表指向所有已处理的子级）

现在您只需分配子级的指针即可当父级处理完成时，您只需使子级成为父级以处理下一级，

以下是我的代码：

//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;
    }