假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
我发现了一个非常漂亮的递归(甚至函数)宽度优先遍历相关算法。不是我的想法,但我认为在这个话题中应该提到它。
Chris Okasaki在http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html上用3张图片非常清楚地解释了他的ICFP 2000的宽度优先编号算法。
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
}
其他回答
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);
}
设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)
我找不到一种完全递归的方法(没有任何辅助数据结构)。但是如果队列Q是通过引用传递的,那么你可以得到下面这个愚蠢的尾部递归函数:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
我发现了一个非常漂亮的递归(甚至函数)宽度优先遍历相关算法。不是我的想法,但我认为在这个话题中应该提到它。
Chris Okasaki在http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html上用3张图片非常清楚地解释了他的ICFP 2000的宽度优先编号算法。
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
}
#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;
}