Предположим, вы решили реализовать рекурсивный поиск двоичного дерева в ширину. Как бы вы это сделали?
Возможно ли использовать только стек вызовов как вспомогательное хранилище?
Выполнение пятого поиска первого поиска рекурсивно
Ответ 1
(Я предполагаю, что это всего лишь какие-то мыслительные упражнения или даже вопрос о домашнем задании/интервью с трюком, но я полагаю, что могу представить себе какой-то странный сценарий, когда по какой-то причине вам не разрешено какое-либо место для кучи [некоторые очень плохой пользовательский менеджер памяти? некоторые странные проблемы с запуском/ОС?], пока у вас все еще есть доступ к стеку...)
Обходной путь в первом порядке традиционно использует очередь, а не стек. Характер очереди и стека в значительной степени противоположный, поэтому попытка использовать стек вызовов (который представляет собой стек, отсюда и название), поскольку вспомогательное хранилище (очередь) в значительной степени обречено на провал, если вы не делаете что-то глупо смешное с стеком вызовов, которого вы не должны быть.
В то же время характер любой нерегулярной рекурсии, которую вы пытаетесь реализовать, по существу добавляет стек к алгоритму. Это делает его не более длинным первым поиском на двоичном дереве, и, таким образом, время выполнения и многое другое для традиционной BFS больше не применяются полностью. Конечно, вы всегда можете тривиально превратить любой цикл в рекурсивный вызов, но это не какая-то значимая рекурсия.
Однако, как показывают другие, есть способы реализовать что-то, что следует за семантикой BFS за небольшую плату. Если стоимость сравнения дорогая, но node обход дешево, то как @Simon Buchan, вы можете просто запустить итеративный поиск по глубине, только обрабатывая листья. Это означало бы отсутствие растущей очереди в куче, только локальную переменную глубины, и стеки, которые постоянно наращиваются в стеке вызовов, когда дерево перемещается снова и снова. И как отметил @Patrick, двоичное дерево, поддерживаемое массивом, как правило, хранится в порядке прохождения в ширину в любом случае, поэтому поиск по ширине в этом случае будет тривиальным, также не требуя дополнительной очереди.
Ответ 2
Если вы используете массив для обратного преобразования двоичного дерева, вы можете определить следующий node алгебраически. если i является node, то его дочерние элементы можно найти в 2i + 1 (для левого node) и 2i + 2 (для правого node). A node следующий сосед задается 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)
Ответ 3
Я не мог найти способ сделать это полностью рекурсивным (без какой-либо вспомогательной структуры данных). Но если очередь Q передается по ссылке, то вы можете иметь следующую глупую хвостовую рекурсивную функцию:
BFS(Q)
{
if (|Q| > 0)
v <- Dequeue(Q)
Traverse(v)
foreach w in children(v)
Enqueue(Q, w)
BFS(Q)
}
Ответ 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;
}
}
Ответ 5
Простая рекурсия BFS и DFS в Java:
Просто нажмите/предложите корень node дерева в стеке/очереди и вызовите эти функции.
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);
}
Ответ 6
Тупой путь:
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;
}
Ответ 7
Я нашел очень красивый рекурсивный (даже функциональный) алгоритм Breadth-First traversal. Не моя идея, но я думаю, что это должно быть упомянуто в этой теме.
Крис Окасаки очень четко объясняет свой алгоритм нумерации по ширине из 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
}
Ответ 8
Здесь реализована реализация 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)
Ответ 9
Здесь Scala 2.11.4 реализация рекурсивной BFS. Я пожертвовал оптимизацией хвостового вызова для краткости, но версия 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]
}
Ответ 10
Следующее кажется мне довольно естественным, используя 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])
Ответ 11
Мне пришлось реализовать обход кучи, который выводится в порядке 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;
}
Ответ 12
Пусть 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)
Ответ 13
BFS для двоичного (или n-арного) дерева можно сделать рекурсивно без очередей следующим образом (здесь в 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));
}
Ответ 14
#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;
}
Ответ 15
Вот реализация JavaScript, которая подделывает первый шаг пересечения с глубиной Первая рекурсия. Я храню значения node на каждой глубине внутри массива внутри хеша. Если уровень уже существует (у нас есть столкновение), мы просто нажимаем на массив на этом уровне. Вы можете использовать массив вместо объекта 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
Ответ 16
Ниже приведен мой код для полностью рекурсивной реализации поиска ширины в двунаправленном графе без использования цикла и очереди.
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);
}
}