假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
愚蠢的方式:
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;
}
其他回答
我发现了一个非常漂亮的递归(甚至函数)宽度优先遍历相关算法。不是我的想法，但我认为在这个话题中应该提到它。
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
}
我已经用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;
}
设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)
我想在上面的答案中加上我的观点，如果语言支持生成器之类的东西，bfs可以协递归地完成。
首先，@Tanzelax的回答是:
宽度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎是相反的，因此试图使用调用堆栈(因此得名为堆栈)作为辅助存储(队列)几乎是注定要失败的
实际上，普通函数调用的堆栈不会像普通堆栈那样运行。但是生成器函数将暂停函数的执行，因此它给了我们产生下一层节点的子节点的机会，而无需深入研究节点的更深层次的后代。
下面的代码是Python中的递归bfs。
def bfs(root):
yield root
for n in bfs(root):
for c in n.children:
yield c
这里的直觉是:
BFS首先将根作为第一个结果返回 假设我们已经有了BFS序列，BFS中的下一层元素是序列中前一个节点的直接子节点 重复以上两个步骤
Here is a JavaScript Implementation that fakes Breadth First Traversal with Depth First recursion. I'm storing the node values at each depth inside an array, inside of a hash. If a level already exists(we have a collision), so we just push to the array at that level. You could use an array instead of a JavaScript object as well since our levels are numeric and can serve as array indices. You can return nodes, values, convert to a Linked List, or whatever you want. I'm just returning values for the sake of simplicity.
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
