以recursion方式执行广度优先search
假设你想实现二叉树的广度优先searchrecursion 。 你将如何去呢？
是否有可能只使用调用栈作为辅助存储？
（我假设这只是某种思维练习，甚至是一个小题作业/面试问题，但是我想我可以想象一些奇怪的场景，出于某种原因你不允许任何堆空间（一些非常不好的习惯内存pipe理器？一些奇怪的运行时/操作系统问题？]，而你仍然可以访问堆栈…）
广度优先遍历传统上使用队列而不是堆栈。 队列和堆栈的本质是相反的，所以试图使用调用堆栈（这是一个堆栈，因此名称）作为辅助存储（队列）是相当注定要失败，除非你在做一些愚蠢的荒谬的调用堆栈，你不应该。
同样的道理，你试图实现的任何非尾recursion的本质实质上是为algorithm增加一个堆栈。 这使得它不再在二叉树上进行宽度优先search，因此传统BFS的运行时间和不再完全适用。 当然，你总是可以轻易地把任何循环变成一个recursion调用，但这不是任何有意义的recursion。
然而，正如其他人所certificate的那样，有些方法是以某种代价来实现遵循BFS的语义。 如果比较的代价是昂贵的，但是节点遍历是便宜的，那么就像@Simon Buchan所做的那样，您可以简单地运行迭代深度优先search，只处理叶子。 这意味着堆中没有增长的队列，只是一个本地的深度variables，并且随着树一遍又一遍遍地遍历，堆栈在调用堆栈上反复build立。 正如@Patrick所指出的那样，一个由数组支持的二叉树通常是以广度优先的遍历顺序存储的，因此对其进行广度优先search将是微不足道的，也不需要辅助队列。
如果使用数组来支持二叉树，则可以以代数方式确定下一个节点。 如果i是一个节点，则可以在2i + 1 （对于左节点）和2i + 2 （对于右节点）find它的子节点。 节点的下一个邻居由i + 1给出，除非i是2的幂
这里是一个非常朴素的数组支持的二叉search树上广度优先search的伪代码。 这假设一个固定大小的数组，因此是一个固定的深度树。 它会看无父母节点，并可能创build一个难以pipe理的大堆栈。
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)
我找不到完全recursion的方法（没有任何辅助数据结构）。 但是如果队列Q通过引用传递，那么你可以有如下愚蠢的尾部recursion函数：
BFS(Q) { if (|Q| > 0) v <- Dequeue(Q) Traverse(v) foreach w in children(v) Enqueue(Q, w) BFS(Q) }
Java中一个简单的BFS和DFSrecursion：
只需在堆栈/队列中推送/提供树的根节点并调用这些函数即可。
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); }
下面的方法使用DFSalgorithm来获取特定深度的所有节点 – 这与为该级别进行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; }
愚蠢的方式：
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() { // acf // be // 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; }
我发现了一个非常漂亮的recursion（甚至function）广度优先遍历相关algorithm。 不是我的想法，但我认为应该在这个话题中提到。
Chris Okasaki非常清楚地解释了他从ICFP 2000开始的宽度优先编号algorithm，只有3张图片在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.htmlfind的是：;
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 }
这是一个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)
这是一个Scala 2.11.4实现的recursionBFS。 为了简洁，我牺牲了tail-call优化，但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] }
下面这些对我来说很自然，使用Haskell。 遍历树的recursion迭代（在这里我收集名字到一个大的有序的string来显示通过树的path）：
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])
我必须实现一个以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; }
设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)
#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; }
这是一个JavaScript的实现，虚假的第一次遍历与深度第一次recursion。 我将数组内的每个深度的节点值存储在一个哈希中。 如果一个关卡已经存在（我们有一个碰撞），所以我们只是推到该层次的数组。 您可以使用数组而不是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
以下是我的代码，完全recursion实现双向图的广度优先search，而不使用循环和队列。
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); } }
