أداء العرض الأول بشكل متكرر

Question

دعنا نقول أنك تريد تنفيذ عملية بحث عن شجرة ثنائية متكرر. كيف يمكنك أن تذهب نحو ذلك؟

هل من الممكن استخدام مكبس المكالمات فقط كسلالة مساعدة؟

Answer 1

(أفترض أن هذا مجرد نوع من ممارسة التفكير ، أو حتى سؤال عن العمل/المقابلة الخدعة ، لكنني أفترض أنني يمكن أن أتخيل بعض السيناريو الغريب حيث لا يُسمح لك بأي مساحة للكومة لسبب ما [بعض العادات السيئة حقًا مدير الذاكرة؟ بعض مشكلات وقت التشغيل/نظام التشغيل الغريب؟] بينما لا يزال بإمكانك الوصول إلى المكدس ...)

يستخدم اجتياز العرض الأول تقليديًا قائمة انتظار ، وليس كومة. إن طبيعة قائمة الانتظار والمكدس معاكسة إلى حد كبير ، لذا فإن محاولة استخدام مكدس الاتصال (وهو عبارة عن مكدس ، ومن ثم الاسم) لأن التخزين المساعد (قائمة انتظار) محكوم عليه بالفشل ، إلا إذا كنت تفعل ذلك شيء مثير للسخرية بغباء مع مكدس الاتصال الذي يجب ألا تكون عليه.

على نفس المنوال ، فإن طبيعة أي عودية غير نيل التي تحاول تنفيذها هي إضافة مكدس إلى الخوارزمية بشكل أساسي. هذا لم يعد يبحث عن الاتساع على شجرة ثنائية ، وبالتالي لم يعد وقت التشغيل وما إلى ذلك ل BFS التقليدية ينطبق تمامًا. بالطبع ، يمكنك دائمًا تحويل أي حلقة إلى مكالمة متكررة ، ولكن هذا ليس نوعًا من العودية ذات المغزى.

ومع ذلك ، هناك طرق ، كما يتضح من الآخرين ، لتنفيذ شيء يتبع دلالات BFS بتكلفة ما. إذا كانت تكلفة المقارنة باهظة الثمن ولكن اجتياز العقدة رخيصة ، فعندئذٍ simon بوكان فعلت ، يمكنك ببساطة تشغيل بحث تكراري للعمق الأول ، فقط معالجة الأوراق. قد يعني هذا عدم وجود قائمة انتظار متزايدة مخزنة في الكومة ، فقط متغير عمق محلي ، ويجري بناء المداخن مرارًا وتكرارًا على مكدس المكالمات حيث يتم اجتياز الشجرة مرارًا وتكرارًا. و كما patrick لوحظ أن شجرة ثنائية مدعومة بصفيف يتم تخزينها عادةً بترتيب اجتياز العرض الأول على أي حال ، وبالتالي فإن البحث الأول عن ذلك سيكون تافهًا ، أيضًا دون الحاجة إلى قائمة انتظار مساعدة.

Answer 2

إذا كنت تستخدم صفيفًا لدعم الشجرة الثنائية ، فيمكنك تحديد العقدة التالية الجبرية. لو i هي عقدة ، ثم يمكن العثور على أطفالها في 2i + 1 (للعقدة اليسرى) و 2i + 2 (للعقدة اليمنى). يتم إعطاء جار العقدة التالي بواسطة i + 1, ، ما لم i هي قوة 2

فيما يلي رمز pseudocode للتنفيذ الساذج للغاية لبحث العرض الأول على شجرة البحث الثنائية المدعومة من مجموعة. هذا يفترض صفيف الحجم الثابت وبالتالي شجرة عمق ثابت. سوف ينظر إلى العقد الوالدية ، ويمكن أن يخلق كومة كبيرة لا يمكن الإدارة.

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)        

Answer 3

لم أتمكن من العثور على طريقة للقيام بذلك متكررة تمامًا (دون أي بنية بيانات مساعدة). ولكن إذا تم تمرير قائمة الانتظار Q بالرجوع إليها ، فيمكنك الحصول على الوظيفة العودية السخيفة التالية:

BFS(Q)
{
  if (|Q| > 0)
     v <- Dequeue(Q)
     Traverse(v)
     foreach w in children(v)
        Enqueue(Q, w)    

     BFS(Q)
}

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

Answer 5

عودية بسيطة من BFS و DFS في Java:
ما عليك سوى دفع/عرض عقدة الجذر للشجرة في المكدس/قائمة الانتظار واستدعاء هذه الوظائف.

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

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

Answer 7

لقد وجدت خوارزمية متعلقة بالتوقيت المتكرر (وحتى وظيفي). ليست فكرتي ، لكنني أعتقد أنه ينبغي ذكرها في هذا الموضوع.

يشرح كريس أوكاساكي خوارزمية الترقيم الأولى من ICFP 2000 في http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html بوضوح شديد مع 3 صور فقط.

تنفيذ Scala لـ Debasish Ghosh ، الذي وجدته في 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
}

Answer 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)

Answer 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]
}

Answer 10

ما يلي يبدو طبيعيا جدا بالنسبة لي ، باستخدام هاسكل. تكرار بشكل متكرر على مستويات الشجرة (هنا أقوم بجمع الأسماء في سلسلة كبيرة مرتبة لإظهار المسار عبر الشجرة):

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])

Answer 11

هنا قصير سكالا المحلول:

  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 12

اضطررت إلى تنفيذ اجتياز الكومة الذي يخرج بترتيب 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 13

دع 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 14

يمكن أن يتم BFS لشجرة ثنائية (أو n-ary) بشكل متكرر بدون طوابير على النحو التالي (هنا في 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 15

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

Answer 16

فيما يلي تطبيق 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 17

فيما يلي الكود الخاص بي للتنفيذ العودية تمامًا للبحث في العرض الأول لرسوم بيانية ثنائية الاتجاه دون استخدام حلقة وقائمة الانتظار.

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 18

فيما يلي تطبيق 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 = []