Breitensuche rekursiv durchführen

151

Angenommen, Sie wollten eine Breitensuche eines Binärbaums rekursiv implementieren . Wie würden Sie vorgehen?

Ist es möglich, nur den Call-Stack als Zusatzspeicher zu verwenden?

Nate
quelle
14
sehr gute Frage. das ist überhaupt nicht einfach. Grundsätzlich möchten Sie ein BFS nur mit einem Stack implementieren.
Sisis
4
rekursiv mit nur einem Stapel? Das tut meinem Kopf weh.
Kevin Friedheim
11
Ich benutze normalerweise einen Stapel, um rekursives Verhalten zu entfernen
Newtopian
Wenn ich BFS auf einem Max-Heap verwende, frage ich mich, ob die unten angegebenen Lösungen ordnungsgemäß funktionieren. Irgendwelche Gedanken?
Jay D

Antworten:

121

(Ich gehe davon aus, dass dies nur eine Art Gedankenübung oder sogar eine Trick-Hausaufgabe / Interview-Frage ist, aber ich nehme an, ich könnte mir ein bizarres Szenario vorstellen, in dem Ihnen aus irgendeinem Grund kein Haufenplatz erlaubt ist [ein wirklich schlechter Brauch Speichermanager - einige bizarre Laufzeit- / Betriebssystemprobleme?], während Sie noch Zugriff auf den Stack haben ...)

Beim Durchlaufen der Breite zuerst wird traditionell eine Warteschlange verwendet, kein Stapel. Die Art einer Warteschlange und eines Stapels ist ziemlich gegensätzlich. Daher ist der Versuch, den Aufrufstapel (der ein Stapel ist, daher der Name) als Hilfsspeicher (eine Warteschlange) zu verwenden, zum Scheitern verurteilt, es sei denn, Sie tun dies etwas dumm Lächerliches mit dem Call Stack, das du nicht sein solltest.

Aus dem gleichen Grund fügt die Art jeder Nicht-Schwanz-Rekursion, die Sie zu implementieren versuchen, im Wesentlichen dem Algorithmus einen Stapel hinzu. Dies führt dazu, dass die erste Suche in einem Binärbaum nicht mehr breit ist und somit die Laufzeit und so weiter für traditionelles BFS nicht mehr vollständig gilt. Natürlich können Sie jede Schleife immer trivial in einen rekursiven Aufruf verwandeln, aber das ist keine sinnvolle Rekursion.

Es gibt jedoch Möglichkeiten, wie von anderen gezeigt, um etwas zu implementieren, das der Semantik von BFS folgt. Wenn die Vergleichskosten teuer sind, die Knotenüberquerung jedoch billig ist, können Sie wie bei @Simon Buchan einfach eine iterative Tiefensuche durchführen und nur die Blätter verarbeiten. Dies würde bedeuten, dass keine wachsende Warteschlange im Heap gespeichert ist, sondern nur eine lokale Tiefenvariable, und dass Stapel auf dem Aufrufstapel immer wieder aufgebaut werden, wenn der Baum immer wieder durchlaufen wird. Und wie @Patrick bemerkte, wird ein Binärbaum, der von einem Array unterstützt wird, normalerweise ohnehin in der Reihenfolge der Breite zuerst durchlaufen, sodass eine Suche in der Breite zuerst trivial wäre, auch ohne dass eine zusätzliche Warteschlange erforderlich wäre.

Tanzelax
quelle
10
Dies ist in der Tat nur eine Gedankenübung. Ich kann mir keine Situation vorstellen, in der Sie dies tatsächlich tun möchten. Danke für die durchdachte Antwort!
Nate
2
" Aber ich nehme an, ich könnte mir ein bizarres Szenario vorstellen, in dem aus irgendeinem Grund kein Heap-Speicherplatz zulässig ist ": Keine Ahnung, ich kann mir eine eingebettete Umgebung vorstellen, in der nur der Stapel (zusammen mit einem schreibgeschützten Speicherplatz) verfügbar ist (es ist) Eigentlich ist es recht einfach und effizient, Software zu schreiben, ohne den Heap zu verwenden, wenn Sie genau wissen, was Ihr Programm tun wird (was normalerweise bei eingebetteter Software der Fall ist). Also ist es für mich nicht so "bizarr". Vielleicht ungewöhnlich, aber nicht bizarr.
Thomas
Ich denke, dass Ihre Antwort einen Verweis auf diesen Artikel enthalten könnte ( ibm.com/developerworks/aix/library/au-aix-stack-tree-traversal ). Es zeigt eine Implementierung über das, was Sie im zweiten Teil Ihrer Antwort geschrieben haben
einschließlich
25

Wenn Sie ein Array zum Sichern des Binärbaums verwenden, können Sie den nächsten Knoten algebraisch bestimmen. Wenn ies sich um einen Knoten handelt, befinden sich seine untergeordneten Knoten unter 2i + 1(für den linken Knoten) und 2i + 2(für den rechten Knoten). Der nächste Nachbar eines Knotens ist gegeben durch i + 1, es isei denn, es handelt sich um eine Potenz von2

Hier ist der Pseudocode für eine sehr naive Implementierung der Breitensuche in einem Array-gestützten binären Suchbaum. Dies setzt ein Array mit fester Größe und daher einen Baum mit fester Tiefe voraus. Es werden übergeordnete Knoten betrachtet und es kann ein unüberschaubar großer Stapel erstellt werden.

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)        
Patrick McMurchie
quelle
1
Nett. Ich habe die Tatsache übersehen, dass es sich um einen Binärbaum handelt. Die Indizes können mit einem DFS zugewiesen werden. Übrigens, Sie haben im ersten Fall eine falsche Rückgabe vergessen.
Sisis
Ich glaube, ich bevorzuge die Warteschlangenmethode; P. Return false hinzugefügt.
Patrick McMurchie
1
Klug. Die Idee, die Knoten in einem Array zu speichern und algebraisch zu referenzieren, war mir nicht gekommen.
Nate
19

Ich konnte keinen Weg finden, dies vollständig rekursiv zu machen (ohne zusätzliche Datenstruktur). Wenn die Warteschlange Q jedoch als Referenz übergeben wird, können Sie die folgende rekursive Funktion für dumme Schwänze verwenden:

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

     BFS(Q)
}
Sisis
quelle
6
Dies ist eine unnatürliche Methode, um eine rekursive, saubere und korrekte Funktion hinzuzufügen.
Mysterion
Stimme überhaupt nicht zu - ich finde es natürlicher - und auch nützlicher; Sie können diese Methode erweitern, um den Arbeitszustand beim Durchlaufen von Ebenen weiterzugeben
Tom Golden
15

Bei der folgenden Methode wurde ein DFS-Algorithmus verwendet, um alle Knoten in einer bestimmten Tiefe abzurufen. Dies entspricht der Ausführung von BFS für diese Ebene. Wenn Sie die Tiefe des Baums herausfinden und dies für alle Ebenen tun, sind die Ergebnisse dieselben wie bei einem 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);
}

Die Tiefe eines Baumes zu finden ist ein Kinderspiel:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}
Sanj
quelle
Bitte achten Sie etwas mehr auf Ihre Code-Formatierung. Ich habe einige Änderungen vorgenommen.
Micha
Aber Moment mal ... ist das eher eine DFS als eine BFS? Weil PrintLevelNodes erst zurückgibt, wenn levelNull ist.
Herrington Darkholme
1
@HerringtonDarkholme, richtig. Es führt eine DFS-Suche durch, gibt jedoch Werte aus, als ob es ein BFS für eine Ebene durchgeführt hätte. Vielen Dank für den Hinweis.
Sanj
1
@ Sanjay, dies ist in der Tat eine gute Demonstration, wie man eine Aktion auf Knoten in DFS-Reihenfolge ausführen kann. Es ist nicht unbedingt so, wie man Knoten in DFS-Reihenfolge tatsächlich "berühren" würde, aber es wird sicherlich möglich sein, rekursiv auf Knoten in DFS-Reihenfolge "einzuwirken", in diesem Fall ihre Werte zu drucken.
Bunkerdive
8

Eine einfache BFS- und DFS-Rekursion in Java: Drücken Sie einfach den Stammknoten
des Baums in den Stapel / die Warteschlange und rufen Sie diese Funktionen auf.

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);
}
ThePatelGuy
quelle
4
Es ist etwas seltsam, Stack als Parameter für DFS zu übergeben, da Sie dort bereits einen impliziten Stack haben. Die Frage war auch, nur den Aufrufstapel als Datenstruktur zu verwenden.
Vladich
4

Ich fand einen sehr schönen rekursiven (sogar funktionalen) Breadth-First-Traversal-bezogenen Algorithmus. Nicht meine Idee, aber ich denke, es sollte in diesem Thema erwähnt werden.

Chris Okasaki erklärt seinen breitesten Nummerierungsalgorithmus aus ICFP 2000 unter http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html sehr deutlich mit nur 3 Bildern.

Die Scala-Implementierung von Debasish Ghosh, die ich unter http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html gefunden habe , lautet:

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
}
snv
quelle
+1 für den schönen Algorithmus. Ich fand es jedoch immer noch in einer Warteschlange. Die linke Seite von "Regel 3" selbst ist eigentlich die Dequeue- und Enqueue-Operation.
Luke Lee
3

Der dumme Weg:

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;
}
Simon Buchan
quelle
3

Hier ist eine kurze Scala- Lösung:

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

Die Idee , den Rückgabewert als Akkumulator zu verwenden, ist gut geeignet. Kann auf ähnliche Weise in anderen Sprachen implementiert werden. Stellen Sie nur sicher, dass Ihre rekursive Funktion die Liste der Knoten verarbeitet .

Auflistung der Testcodes (unter Verwendung des @ marco-Testbaums):

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

Ausgabe:

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

Hier ist eine Python-Implementierung:

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)
Anfänger
quelle
2

Hier ist eine Scala 2.11.4-Implementierung von rekursivem BFS. Ich habe der Kürze halber die Tail-Call-Optimierung geopfert, aber die TCOd-Version ist sehr ähnlich. Siehe auch den Beitrag von @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]
}
Joffer
quelle
2

Das Folgende scheint mir mit Haskell ziemlich natürlich zu sein. Iterieren Sie rekursiv über Ebenen des Baums (hier sammle ich Namen in einer großen geordneten Zeichenfolge, um den Pfad durch den Baum anzuzeigen):

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

quelle
2

Hier ist eine rekursive BFS-Traversal-Python-Implementierung, die für ein Diagramm ohne Zyklus arbeitet.

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 = []
Jbeat
quelle
2

Ich möchte meine Cent zur Top-Antwort hinzufügen , dass bfs rekursiv ausgeführt werden kann, wenn die Sprache so etwas wie Generator unterstützt.

Die Antwort von @ Tanzelax lautet zunächst:

Beim Durchlaufen der Breite zuerst wird traditionell eine Warteschlange verwendet, kein Stapel. Die Art einer Warteschlange und eines Stapels ist ziemlich gegensätzlich, so dass der Versuch, den Aufrufstapel (der ein Stapel ist, daher der Name) als Hilfsspeicher (eine Warteschlange) zu verwenden, zum Scheitern verurteilt ist

In der Tat verhält sich der Stapel eines normalen Funktionsaufrufs nicht wie ein normaler Stapel. Die Generatorfunktion unterbricht jedoch die Ausführung der Funktion, sodass wir die Möglichkeit haben, die nächste Ebene der untergeordneten Knoten zu erhalten, ohne auf tiefere Nachkommen des Knotens einzugehen.

Der folgende Code ist rekursives bfs in Python.

def bfs(root):
  yield root
  for n in bfs(root):
    for c in n.children:
      yield c

Die Intuition hier ist:

  1. bfs first gibt die Wurzel als erstes Ergebnis zurück
  2. Angenommen, wir haben bereits die bfs-Sequenz. Die nächste Ebene der Elemente in bfs sind die unmittelbaren untergeordneten Elemente des vorherigen Knotens in der Sequenz
  3. Wiederholen Sie die beiden oben genannten Schritte
Herrington Darkholme
quelle
Ich kenne Python nicht, aber ich denke, Ihr Code wird in diesen C # -Code übersetzt . Es führt die BFS-Durchquerung durch, stürzt jedoch mit einer Stackoverflow-Ausnahme ab. Ich habe bisher nicht herausgefunden, warum. Ich habe den Algorithmus jedoch so geändert, dass er stoppt (und wahrscheinlich eine bessere Leistung erbringt). Mein Arbeitsprobe finden Sie hier .
Adam Simon
1

Ich musste einen Heap-Traversal implementieren, der in einer BFS-Reihenfolge ausgegeben wird. Es ist eigentlich kein BFS, erfüllt aber die gleiche Aufgabe.

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;
}
Justin
quelle
2
Für andere Betrachter: Dies ist ein Beispiel für die Implementierung eines vollständigen Baums in einem Array. Insbesondere führt @Justin eine Vorbestellungsdurchquerung durch, bei der er Knotenwerte (in BFS-Reihenfolge) in einem Array am entsprechenden BFS-Index speichert. Dadurch kann die aufrufende Funktion linear durch das Array iterieren und Werte in der BFS-Reihenfolge drucken. Siehe diese allgemeine Beschreibung. Hinweis: Die aufrufende Funktion muss den Fall nicht vollständiger Bäume behandeln.
Bunkerdive
1

Sei v der Startpunkt

Sei G der fragliche Graph

Das Folgende ist der Pseudocode ohne Verwendung der Warteschlange

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)
Ashok
quelle
Ich denke, dies könnte in einer Endlosschleife stecken bleiben - die Eckpunkte werden als besucht markiert, aber sie werden nie auf Besuch geprüft, bevor sie erneut rekursiv sind.
Dieses Snippet ähnelt eher DFS als BFS
Dení
1

BFS für einen binären (oder n-ary) Baum kann wie folgt rekursiv ohne Warteschlangen ausgeführt werden (hier in 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;
    }
}

Ein Beispiel für das Durchlaufen von Drucknummern 1-12 in aufsteigender Reihenfolge:

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));
}
marco
quelle
0
#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;
}
Kaidul
quelle
0

Hier ist eine JavaScript-Implementierung, die Breadth First Traversal mit Depth First-Rekursion vortäuscht. Ich speichere die Knotenwerte in jeder Tiefe innerhalb eines Arrays, innerhalb eines Hashs. Wenn bereits eine Ebene vorhanden ist (wir haben eine Kollision), drücken wir einfach auf das Array auf dieser Ebene. Sie können auch ein Array anstelle eines JavaScript-Objekts verwenden, da unsere Ebenen numerisch sind und als Array-Indizes dienen können. Sie können Knoten, Werte zurückgeben, in eine verknüpfte Liste konvertieren oder was auch immer Sie möchten. Der Einfachheit halber gebe ich nur Werte zurück.

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 ] } */

Hier ist ein Beispiel für die tatsächliche erste Durchquerung der Breite unter Verwendung eines iterativen Ansatzes.

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
Alex Hawkins
quelle
0

Das Folgende ist mein Code für die vollständig rekursive Implementierung der Breitensuche eines bidirektionalen Graphen ohne Verwendung von Schleife und Warteschlange.

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

Pushkal
quelle
0

C # -Implementierung eines rekursiven Breitensuchalgorithmus für einen Binärbaum.

Visualisierung von Binärbaumdaten

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

Wenn Sie möchten, dass der Algorithmus nicht nur mit dem Binärbaum, sondern auch mit Diagrammen funktioniert, die zwei und mehr Knoten haben können, die auf denselben anderen Knoten verweisen, müssen Sie das Selbstzyklus vermeiden, indem Sie die Liste der bereits besuchten Knoten halten. Die Implementierung sieht möglicherweise so aus.

Grafikdatenvisualisierung

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();
    });
}
v.vyhonskyi
quelle
0

Ich habe ein Programm mit c ++ erstellt, das auch in gemeinsamen und disjunkten Graphen funktioniert.

    #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;
}
Arpan Sahu
quelle