Rekurencyjne wykonywanie pierwszego przeszukiwania wszerz

152

Załóżmy, że chcesz zaimplementować rekurencyjne przeszukiwanie wszerz drzewa binarnego . Jak byś się do tego zabrał?

Czy jest możliwe używanie tylko stosu wywołań jako pamięci dyskowej?

Nate
źródło
14
bardzo dobre pytanie. nie jest to wcale proste. w zasadzie prosisz o implementację BFS używając tylko stosu.
sisis
4
rekurencyjnie z samym stosem? to boli mnie w głowę.
Kevin Friedheim
11
Zwykle używam stosu, aby usunąć zachowanie rekurencyjne
Newtopian
Jeśli używam BFS na stercie Max, zastanawiam się, czy poniższe rozwiązania działają poprawnie? Jakieś pomysły ?
Jay D

Odpowiedzi:

122

(Zakładam, że to tylko jakieś ćwiczenie myślowe, a nawet podchwytliwe zadanie domowe / pytanie do rozmowy kwalifikacyjnej, ale przypuszczam, że mógłbym sobie wyobrazić jakiś dziwny scenariusz, w którym z jakiegoś powodu nie masz miejsca na sterty [jakiś naprawdę zły zwyczaj menadżer pamięci? jakieś dziwne problemy ze środowiskiem wykonawczym / systemem operacyjnym?], podczas gdy nadal masz dostęp do stosu ...)

Przechodzenie wszerz tradycyjnie używa kolejki, a nie stosu. Natura kolejki i stosu jest prawie przeciwna, więc próba użycia stosu wywołań (który jest stosem, stąd nazwa) jako pamięci dyskowej (kolejki) jest prawie skazana na niepowodzenie, chyba że robisz coś głupiego absurdalnego ze stosem wywołań, którym nie powinieneś być.

Z tego samego powodu naturą każdej rekursji innej niż ogon, którą próbujesz zaimplementować, jest zasadniczo dodanie stosu do algorytmu. To sprawia, że ​​pierwsze przeszukiwanie w drzewie binarnym nie jest już obszerne, a tym samym czas wykonywania i inne elementy tradycyjnego BFS nie mają już pełnego zastosowania. Oczywiście zawsze można w trywialny sposób przekształcić dowolną pętlę w wywołanie rekurencyjne, ale nie jest to żadna sensowna rekurencja.

Istnieją jednak sposoby, jak pokazali inni, aby zaimplementować coś, co jest zgodne z semantyką BFS za pewną cenę. Jeśli koszt porównania jest drogi, ale przemierzanie węzłów jest tanie, to tak jak zrobił to @Simon Buchan , możesz po prostu uruchomić iteracyjne przeszukiwanie w głąb, przetwarzając tylko liście. Oznaczałoby to brak rosnącej kolejki przechowywanej w stercie, tylko lokalną zmienną głębokości, a stosy są budowane w kółko na stosie wywołań, gdy drzewo jest przechodzone w kółko. I jak zauważył @Patrick , drzewo binarne wspierane przez tablicę jest zwykle przechowywane w kolejności przechodzenia wszerz, więc przeszukiwanie wszerz byłoby trywialne, również bez kolejki pomocniczej.

Tanzelax
źródło
10
To rzeczywiście tylko ćwiczenie myślowe. Naprawdę nie mogę sobie wyobrazić sytuacji, w której chciałbyś to zrobić. Dzięki za przemyślaną odpowiedź!
Nate
2
ale przypuszczam, że mógłbym sobie wyobrazić jakiś dziwaczny scenariusz, w którym z jakiegoś powodu nie jest dozwolone żadne miejsce na stosie ”: nie wiem, mogę sobie wyobrazić osadzone środowisko, w którym dostępny jest tylko stos (wraz z przestrzenią pamięci tylko do odczytu) (jest to w rzeczywistości całkiem łatwe i wydajne pisanie oprogramowania bez użycia sterty w ogóle, jeśli wiesz dokładnie, co ma zrobić twój program, co zwykle ma miejsce w oprogramowaniu wbudowanym). Więc nie jest to dla mnie takie „dziwne”. Może nietypowe, ale nie dziwne.
Thomas,
Myślę, że Twoja odpowiedź może zawierać odniesienie do tego artykułu ( ibm.com/developerworks/aix/library/au-aix-stack-tree-traversal ). Pokazuje implementację tego, co napisałeś w drugiej części swojej odpowiedzi
tym
25

Jeśli używasz tablicy do tworzenia kopii zapasowej drzewa binarnego, możesz algebraicznie określić następny węzeł. jeśli ijest węzłem, to jego dzieci można znaleźć w 2i + 1(dla lewego węzła) i 2i + 2(dla prawego węzła). Następny sąsiad węzła jest określany przez i + 1, chyba że ijest to potęga2

Oto pseudokod dla bardzo naiwnej implementacji pierwszego przeszukiwania wszerz w binarnym drzewie wyszukiwania opartym na tablicy. Zakłada to tablicę o stałym rozmiarze, a zatem drzewo o stałej głębokości. Będzie patrzeć na węzły bez rodzica i może stworzyć niemożliwy do zarządzania duży stos.

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
źródło
1
Miły. Przeoczyłem fakt, że mamy do czynienia z drzewem binarnym. Indeksy można przypisać za pomocą DFS. BTW, zapomniałeś o zwrotnym fałszu w pierwszym przypadku.
sisis
Myślę, że wolę metodę kolejkowania; P. Dodano zwrot false.
Patrick McMurchie
1
Sprytny. Pomysł przechowywania węzłów w tablicy i odwoływania się do nich algebraicznie nie przyszedł mi do głowy.
Nate
19

Nie mogłem znaleźć sposobu, aby zrobić to całkowicie rekurencyjnie (bez żadnej pomocniczej struktury danych). Ale jeśli kolejka Q jest przekazywana przez referencję, możesz mieć następującą rekurencyjną funkcję głupiego ogona:

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

     BFS(Q)
}
sisis
źródło
6
Jest to nienaturalny sposób dodawania rekurencyjnych do czystych i poprawnych funkcji.
Mysterion
Całkowicie się nie zgadzam - uważam to za bardziej naturalne - a także bardziej przydatne; możesz rozszerzyć tę metodę, aby przekazywać stan roboczy podczas przechodzenia przez warstwy
Tom Golden
15

W poniższej metodzie zastosowano algorytm DFS, aby uzyskać wszystkie węzły na określonej głębokości - co jest takie samo jak wykonanie BFS dla tego poziomu. Jeśli znajdziesz głębokość drzewa i zrobisz to na wszystkich poziomach, wyniki będą takie same jak w przypadku 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);
}

Znalezienie głębokości drzewa to bułka z masłem:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}
Sanj
źródło
Zwróć trochę więcej uwagi na formatowanie kodu. Zrobiłem kilka zmian.
Micha
Ale poczekaj ... czy to jest raczej DFS niż BFS? Ponieważ PrintLevelNodes nie zwraca do levelzera.
Herrington Darkholme
1
@HerringtonDarkholme, poprawnie. Wyszukuje DFS, ale wartości wyjściowe tak, jakby wykonywał BFS dla poziomu. Dzięki za zwrócenie uwagi.
Sanj
1
@Sanjay, to rzeczywiście dobra demonstracja tego, jak można wykonać jakąś akcję na węzłach w kolejności DFS. Niekoniecznie jest to, w jaki sposób można faktycznie „dotykać” węzłów w kolejności DFS, ale z pewnością pozwoli na rekurencyjne „działanie” na węzłach w kolejności DFS, w tym przypadku drukowanie ich wartości.
nurkowanie z bunkrem,
8

Prosta rekurencja BFS i DFS w Javie: po
prostu wypchnij / zaoferuj węzeł główny drzewa w stosie / kolejce i wywołaj te funkcje.

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
źródło
4
Przekazywanie stosu jako parametru dla DFS jest trochę dziwne, ponieważ masz już tam niejawny stos. Chodziło również o użycie tylko stosu wywołań jako struktury danych.
vladich
4

Znalazłem bardzo piękny, rekurencyjny (a nawet funkcjonalny) algorytm związany z przemierzaniem Breadth-First. Nie mój pomysł, ale myślę, że należy o tym wspomnieć w tym temacie.

Chris Okasaki bardzo wyraźnie wyjaśnia swój algorytm numeracji wszerz z ICFP 2000 pod adresem http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html za pomocą tylko 3 zdjęć.

Implementacja Debasish Ghosh w Scali, którą znalazłem pod adresem http://debasishg.blogspot.de/2008/09/breadth-first-numbering-okasakis.html , to:

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
źródło
+1 za piękny algorytm. Jednak okazało się, że nadal korzysta z kolejki. Lewa strona „Reguły 3” jest w rzeczywistości operacjami usuwania z kolejki i umieszczania w kolejce.
Luke Lee
3

Głupi sposób:

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
źródło
3

Oto krótkie rozwiązanie Scala :

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

Pomysł wykorzystania wartości zwracanej jako akumulatora jest dobrze dopasowany. Może być zaimplementowany w innych językach w podobny sposób, po prostu upewnij się, że Twoja rekurencyjna funkcja przetwarza listę węzłów .

Listing kodu testowego (przy użyciu drzewa testowego @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())))
  }
}

Wynik:

List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
Ilya Bystrov
źródło
2

Oto implementacja Pythona:

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)
rekrut
źródło
2

Oto implementacja rekurencyjnego BFS w Scali 2.11.4. Poświęciłem optymalizację wywołań ogonowych dla zwięzłości, ale wersja TCOd jest bardzo podobna. Zobacz także post @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
źródło
2

Poniższe wydaje mi się całkiem naturalne, używając Haskella. Iteruj rekurencyjnie po poziomach drzewa (tutaj zbieram nazwy w duży uporządkowany ciąg, aby pokazać ścieżkę przez drzewo):

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

źródło
2

Oto implementacja Pythona z rekurencyjnym przechodzeniem przez BFS, pracująca dla wykresu bez cyklu.

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
źródło
2

Chciałbym dodać moje centy do górnej odpowiedzi, ponieważ jeśli język obsługuje coś takiego jak generator, bfs można wykonać ko-rekurencyjnie.

Na początek odpowiedź @ Tanzelax brzmi:

Przechodzenie wszerz tradycyjnie używa kolejki, a nie stosu. Charakter kolejki i stosu są prawie przeciwne, więc próba użycia stosu wywołań (który jest stosem, stąd nazwa) jako magazynu pomocniczego (kolejki) jest prawie skazana na niepowodzenie

Rzeczywiście, zwykły stos wywołań funkcji nie będzie zachowywał się jak zwykły stos. Ale funkcja generatora zawiesi wykonywanie funkcji, więc daje nam szansę na uzyskanie następnego poziomu dzieci węzłów bez zagłębiania się w głębsze potomstwo węzła.

Poniższy kod jest rekurencyjnym bfs w Pythonie.

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

Oto intuicja:

  1. bfs first zwróci root jako pierwszy wynik
  2. załóżmy, że mamy już sekwencję bfs, następny poziom elementów w bfs to bezpośrednie dzieci poprzedniego węzła w sekwencji
  3. powtórz powyższe dwie procedury
Herrington Darkholme
źródło
Nie znam Pythona, ale myślę, że twój kod przekłada się na ten kod C # . Wykonuje przeszukiwanie BFS, ale ulega awarii z wyjątkiem przepełnienia stosu. Jak dotąd nie doszedłem do wniosku, dlaczego. Jednak zmodyfikowałem algorytm, aby się zatrzymywał (i prawdopodobnie działa lepiej). Znajdziesz moją próbkę roboczą tutaj .
Adam Simon
1

Musiałem zaimplementować przemierzanie sterty, które generuje w kolejności BFS. W rzeczywistości nie jest to BFS, ale spełnia to samo zadanie.

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
źródło
2
Dla innych widzów: to jest przykład implementacji pełnego drzewa w tablicy; W szczególności @Justin wykonuje przegląd przed zamówieniem, podczas którego zapisuje wartości węzłów (w kolejności BFS) w tablicy w odpowiednim indeksie BFS. Pozwala to funkcji wywołującej na iterację liniową po tablicy, wypisując wartości w kolejności BFS. Zobacz ten ogólny opis Uwaga: funkcja wywołująca musi obsługiwać przypadek niekompletnych drzew.
nurkowanie z bunkrem
1

Niech v będzie wierzchołkiem początkowym

Niech G będzie danym wykresem

Poniżej znajduje się pseudokod bez użycia kolejki

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
źródło
Myślę, że może to utknąć w nieskończonej pętli - wierzchołki są oznaczane jako odwiedzone, ale nigdy nie są testowane pod kątem odwiedzalności przed ponownym powtórzeniem.
Ten fragment jest podobny do DFS, a nie BFS
Dení
1

BFS dla drzewa binarnego (lub n-arnego) można wykonać rekurencyjnie bez kolejek w następujący sposób (tutaj w Javie):

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

Przykładowy wydruk przechodzenia od 1 do 12 w kolejności rosnącej:

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
źródło
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
źródło
0

Oto implementacja JavaScript, która fałszuje Breadth First Traversal z rekursją Depth First. Przechowuję wartości węzłów na każdej głębokości wewnątrz tablicy, wewnątrz skrótu. Jeśli poziom już istnieje (mamy kolizję), po prostu wypychamy do tablicy na tym poziomie. Możesz użyć tablicy zamiast obiektu JavaScript, ponieważ nasze poziomy są numeryczne i mogą służyć jako indeksy tablic. Możesz zwrócić węzły, wartości, przekonwertować na listę połączoną lub cokolwiek chcesz. Zwracam wartości ze względu na prostotę.

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

Oto przykład rzeczywistego pierwszego przejścia szerokości przy użyciu podejścia iteracyjnego.

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
źródło
0

Poniżej znajduje się mój kod do całkowicie rekurencyjnej implementacji przeszukiwania wszerz dwukierunkowego wykresu bez używania pętli i kolejki.

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
źródło
0

Implementacja C # rekurencyjnego algorytmu wyszukiwania wszerz dla drzewa binarnego.

Wizualizacja danych drzewa binarnego

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

Jeśli chcesz, aby algorytm działał nie tylko z drzewem binarnym, ale z wykresami, które mogą mieć dwa i więcej węzłów wskazujących na ten sam inny węzeł, musisz uniknąć samokontroli, utrzymując listę już odwiedzonych węzłów. Implementacja może wyglądać tak.

Wizualizacja danych graficznych

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
źródło
0

Zrobiłem program przy użyciu C ++, który działa również na wykresie połączonym i rozłącznym.

    #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
źródło