Выполнение поиска в ширину рекурсивно

Question

Допустим, вы хотели реализовать поиск в двоичном формате в ширину рекурсивно .Как бы вы поступили?

Возможно ли использовать только стек вызовов в качестве вспомогательного хранилища?

Answer 1

Вот кратко Scala решение:

  def bfs(nodes: List[Node]): List[Node] = {
    if (nodes.nonEmpty) {
      nodes ++ bfs(nodes.flatMap(_.children))
    } else {
      List.empty
    }
  }

Идея с использованием возвращаемого значения в качестве аккумулятора хорошо подходит. Может быть реализован на других языках аналогичным образом, просто убедитесь, что ваша рекурсивная функция обрабатывает список узлов .

Список тестовых кодов (с использованием тестового дерева @marco):

import org.scalatest.FlatSpec

import scala.collection.mutable

class Node(val value: Int) {

  private val _children: mutable.ArrayBuffer[Node] = mutable.ArrayBuffer.empty

  def add(child: Node): Unit = _children += child

  def children = _children.toList

  override def toString: String = s"$value"
}

class BfsTestScala extends FlatSpec {

  //            1
  //          / | \
  //        2   3   4
  //      / |       | \
  //    5   6       7  8
  //  / |           | \
  // 9  10         11  12
  def tree(): Node = {
    val root = new Node(1)
    root.add(new Node(2))
    root.add(new Node(3))
    root.add(new Node(4))
    root.children(0).add(new Node(5))
    root.children(0).add(new Node(6))
    root.children(2).add(new Node(7))
    root.children(2).add(new Node(8))
    root.children(0).children(0).add(new Node(9))
    root.children(0).children(0).add(new Node(10))
    root.children(2).children(0).add(new Node(11))
    root.children(2).children(0).add(new Node(12))
    root
  }

  def bfs(nodes: List[Node]): List[Node] = {
    if (nodes.nonEmpty) {
      nodes ++ bfs(nodes.flatMap(_.children))
    } else {
      List.empty
    }
  }

  "BFS" should "work" in {
    println(bfs(List(tree())))
  }
}

Выход:

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)

Answer 2

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));
}

Answer 3

Мне пришлось реализовать обход кучи, который выводит в порядке 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;
}

Answer 4

Пусть 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)

Answer 5

Вот реализация Python для рекурсивного обхода BFS, работающая для графа без цикла.

def bfs_recursive(level):
    '''
     @params level: List<Node> containing the node for a specific level.
    '''
    next_level = []
    for node in level:
        print(node.value)
        for child_node in node.adjency_list:
            next_level.append(child_node)
    if len(next_level) != 0:
        bfs_recursive(next_level)


class Node:
    def __init__(self, value):
        self.value = value
        self.adjency_list = []

Answer 6

Ниже приведен мой код для полностью рекурсивной реализации поиска в ширину двунаправленного графа без использования цикла и очереди.

</p>

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);
        }
    }

Answer 7

Вот реализация JavaScript, которая имитирует обход в ширину и рекурсию в глубину. Я храню значения узлов на каждой глубине внутри массива, внутри хеша. Если уровень уже существует (у нас есть коллизия), поэтому мы просто перемещаемся к массиву на этом уровне. Вы также можете использовать массив вместо объекта 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

Answer 8

#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;
}