假设您想递归地实现一个二叉树的宽度优先搜索。你会怎么做?
是否可以只使用调用堆栈作为辅助存储?
当前回答
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;
}
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();
});
}
下面使用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])
(我假设这只是某种思维练习，或者甚至是一个恶作剧的家庭作业/面试问题，但是我想我可以想象一些奇怪的场景，由于某种原因不允许有任何堆空间[一些非常糟糕的自定义内存管理器?一些奇怪的运行时/操作系统问题?当你仍然可以访问堆栈时…)
宽度优先遍历传统上使用队列，而不是堆栈。队列和堆栈的性质几乎是相反的，因此试图使用调用堆栈(这是一个堆栈，因此得名)作为辅助存储(队列)几乎是注定要失败的，除非您对调用堆栈做了一些不应该做的愚蠢可笑的事情。
同样，您尝试实现的任何非尾递归本质上都是向算法添加堆栈。这使得它不再在二叉树上进行广度优先搜索，因此传统BFS的运行时和诸如此类的东西不再完全适用。当然，您总是可以简单地将任何循环转换为递归调用，但这并不是任何有意义的递归。
However, there are ways, as demonstrated by others, to implement something that follows the semantics of BFS at some cost. If the cost of comparison is expensive but node traversal is cheap, then as @Simon Buchan did, you can simply run an iterative depth-first search, only processing the leaves. This would mean no growing queue stored in the heap, just a local depth variable, and stacks being built up over and over on the call stack as the tree is traversed over and over again. And as @Patrick noted, a binary tree backed by an array is typically stored in breadth-first traversal order anyway, so a breadth-first search on that would be trivial, also without needing an auxiliary queue.
#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;
}
