Pertunjukan Breadth First Search secara rekursif

152

Katakanlah Anda ingin mengimplementasikan pencarian pertama dari pohon biner secara rekursif . Bagaimana Anda melakukannya?

Apakah mungkin hanya menggunakan tumpukan panggilan sebagai penyimpanan tambahan?

Nate
sumber
14
pertanyaan yang sangat bagus ini tidak langsung sama sekali. pada dasarnya Anda meminta untuk mengimplementasikan BFS hanya menggunakan tumpukan.
sisis
4
secara rekursif hanya dengan setumpuk? ini menyakitkan kepalaku.
Kevin Friedheim
11
Saya biasanya menggunakan tumpukan untuk menghapus perilaku rekursif
Newtopian
Jika saya menggunakan BFS pada tumpukan Max, saya ingin tahu apakah solusi yang diberikan di bawah ini berfungsi dengan baik? Adakah pikiran?
Jay D

Jawaban:

123

(Saya berasumsi bahwa ini hanya semacam latihan pemikiran, atau bahkan trik mengerjakan pekerjaan rumah / wawancara, tapi saya kira saya bisa membayangkan beberapa skenario aneh di mana Anda tidak diizinkan menimbun ruang untuk beberapa alasan [beberapa kebiasaan yang sangat buruk manajer memori? beberapa masalah runtime / OS yang aneh?] ketika Anda masih memiliki akses ke tumpukan ...)

Breadth-first traversal secara tradisional menggunakan antrian, bukan tumpukan. Sifat antrian dan tumpukan cukup berlawanan, jadi mencoba menggunakan panggilan stack (yang merupakan tumpukan, maka nama) sebagai penyimpanan tambahan (antrian) cukup banyak ditakdirkan untuk gagal, kecuali jika Anda melakukan sesuatu yang konyol dengan tumpukan panggilan yang seharusnya tidak Anda lakukan.

Pada token yang sama, sifat dari setiap rekursi non-ekor yang Anda coba implementasikan pada dasarnya menambahkan tumpukan ke algoritma. Ini membuatnya tidak lagi luas pencarian pertama pada pohon biner, dan dengan demikian run-time dan yang lainnya untuk BFS tradisional tidak lagi sepenuhnya berlaku. Tentu saja, Anda selalu dapat dengan mudah mengubah perulangan apa pun menjadi panggilan rekursif, tetapi itu bukan jenis rekursi yang berarti.

Namun, ada cara, seperti yang ditunjukkan oleh orang lain, untuk mengimplementasikan sesuatu yang mengikuti semantik BFS dengan biaya tertentu. Jika biaya perbandingannya mahal tetapi node traversal murah, maka seperti yang dilakukan @Simon Buchan , Anda bisa menjalankan pencarian kedalaman-iteratif pertama, hanya memproses daun. Ini berarti tidak ada antrian tumbuh yang disimpan di heap, hanya variabel kedalaman lokal, dan tumpukan yang dibangun berulang-ulang di tumpukan panggilan saat pohon dilintasi berulang-ulang. Dan seperti yang dicatat oleh @Patrick , pohon biner yang didukung oleh array biasanya disimpan dalam urutan traversal pertama, jadi pencarian pertama yang luas akan sepele, juga tanpa perlu antrian tambahan.

Tanzelax
sumber
10
Ini memang hanya latihan pikiran. Saya tidak dapat membayangkan situasi di mana Anda sebenarnya ingin melakukan ini. Terima kasih atas jawaban yang dipikirkan dengan matang!
Nate
2
" tapi saya kira saya bisa membayangkan beberapa skenario aneh di mana Anda tidak diizinkan menimbun ruang untuk beberapa alasan ": tak tahu, saya bisa membayangkan lingkungan tertanam di mana hanya tumpukan (bersama dengan ruang memori hanya baca) yang tersedia (itu sebenarnya cukup mudah dan efisien untuk menulis perangkat lunak tanpa menggunakan tumpukan sama sekali jika Anda tahu persis apa yang akan dilakukan program Anda, yang biasanya terjadi pada perangkat lunak yang disematkan). Jadi bukankah itu "aneh" bagi saya. Tidak biasa, mungkin, tetapi tidak aneh.
Thomas
Saya pikir jawaban Anda mungkin berisi referensi ke artikel ini ( ibm.com/developerworks/aix/library/au-aix-stack-tree-traversal ). Ini menunjukkan implementasi tentang apa yang Anda tulis di bagian kedua dari jawaban Anda
termasuk
25

Jika Anda menggunakan array untuk mendukung pohon biner, Anda dapat menentukan simpul berikutnya secara aljabar. jika iadalah simpul, maka anak-anaknya dapat ditemukan di 2i + 1(untuk simpul kiri) dan 2i + 2(untuk simpul kanan). Tetangga node berikutnya diberikan oleh i + 1, kecuali ikekuatan dari2

Inilah pseudocode untuk implementasi yang sangat naif dari pencarian pertama luasnya pada pohon pencarian biner array yang didukung. Ini mengasumsikan array ukuran tetap dan karenanya pohon kedalaman tetap. Ini akan melihat node tanpa orangtua, dan dapat membuat tumpukan besar tidak terkelola.

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
sumber
1
Bagus. Saya mengabaikan fakta bahwa kita berhadapan dengan pohon biner. Indeks dapat ditetapkan menggunakan DFS. BTW, Anda lupa false return pada kasus pertama.
sisis
Saya pikir saya lebih suka metode antrian; P. Menambahkan return false.
Patrick McMurchie
1
Pintar. Gagasan menyimpan node dalam array dan referensi mereka secara aljabar tidak terpikir oleh saya.
Nate
19

Saya tidak dapat menemukan cara untuk melakukannya sepenuhnya rekursif (tanpa struktur data tambahan). Tetapi jika antrian Q dilewatkan dengan referensi, maka Anda dapat memiliki fungsi rekursif ekor konyol berikut:

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

     BFS(Q)
}
sisis
sumber
6
Ini cara yang tidak wajar, untuk menambahkan fungsi rekursif ke bersih dan benar.
Mysterion
Sepenuhnya tidak setuju - saya merasa lebih alami - dan juga lebih bermanfaat; Anda dapat memperluas metode ini untuk menurunkan kondisi kerja saat Anda melewati lapisan
Tom Golden
15

Metode berikut menggunakan algoritma DFS untuk mendapatkan semua node di kedalaman tertentu - yang sama dengan melakukan BFS untuk tingkat itu. Jika Anda menemukan kedalaman pohon dan melakukan ini untuk semua tingkatan, hasilnya akan sama dengan 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);
}

Menemukan kedalaman pohon adalah sepotong kue:

public int MaxDepth(Tree root) {
    if (root == null) {
        return 0;
    } else {
        return Math.Max(MaxDepth(root.Left), MaxDepth(root.Right)) + 1;
    }
}
Sanj
sumber
Mohon sedikit lebih memperhatikan formating kode Anda. Saya melakukan beberapa perubahan.
Micha
Tapi, tunggu dulu ... apakah ini DFS daripada BFS? Karena PrintLevelNodes tidak kembali sampai levelnol.
Herrington Darkholme
1
@ HerringtonDarkholme, Benar. Itu pencarian DFS tetapi nilai-nilai output seolah-olah melakukan BFS untuk tingkat. Terima kasih telah menunjukkan itu.
Sanj
1
@ Sanjay, ini memang demonstrasi yang bagus tentang bagaimana seseorang dapat melakukan beberapa tindakan pada node dalam urutan DFS. Ini tidak selalu bagaimana seseorang akan benar-benar "menyentuh" ​​node dalam urutan DFS, tetapi tentu akan memungkinkan untuk secara "berulang" bertindak pada node dalam urutan DFS, dalam hal ini mencetak nilai-nilai mereka.
bunkerdive
8

Rekursi BFS dan DFS sederhana di Jawa:
Cukup tekan / tawarkan simpul akar pohon di stack / antrian dan panggil fungsi-fungsi ini.

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
sumber
4
Agak aneh untuk melewatkan stack sebagai parameter untuk DFS, karena Anda sudah memiliki stack implisit di sana. Juga pertanyaannya adalah hanya menggunakan stack panggilan sebagai struktur data.
vladich
4

Saya menemukan algoritma terkait Breadth-First traversal terkait rekursif (bahkan fungsional) yang sangat indah. Bukan ide saya, tapi saya pikir itu harus disebutkan dalam topik ini.

Chris Okasaki menjelaskan algoritme penomoran pertamanya yang luas dari ICFP 2000 di http://okasaki.blogspot.de/2008/07/breadth-first-numbering-algorithm-in.html sangat jelas hanya dengan 3 gambar.

Implementasi Scala dari Debasish Ghosh, yang saya temukan di http://debasishg.blogspot.de/2008/09/breadth-first-first-numbering-okasakis.html , adalah:

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
sumber
+1 untuk algoritme yang indah. Namun, saya menemukannya masih menggunakan antrian. Sisi kiri "Aturan 3" itu sendiri sebenarnya adalah operasi dequeue dan enqueue.
Luke Lee
3

Cara bodoh:

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
sumber
3

Inilah solusi Scala singkat :

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

Ide menggunakan nilai kembali sebagai akumulator sangat cocok. Dapat diimplementasikan dalam bahasa lain dengan cara yang sama, hanya pastikan bahwa proses rekursif Anda daftar node .

Daftar kode tes (menggunakan pohon tes @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())))
  }
}

Keluaran:

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

Berikut ini implementasi 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)
calon
sumber
2

Berikut ini adalah implementasi Scala 2.11.4 dari BFS rekursif. Saya telah mengorbankan optimisasi panggilan ekor untuk singkatnya, tetapi versi TCOd sangat mirip. Lihat juga postingan @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
sumber
2

Berikut ini sepertinya cukup alami bagi saya, menggunakan Haskell. Ulangi secara berulang di atas level pohon (di sini saya mengumpulkan nama menjadi string besar yang diperintahkan untuk menunjukkan jalur melalui pohon):

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

sumber
2

Berikut ini adalah implementasi Python traversal rekursif BFS, bekerja untuk grafik tanpa siklus.

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
sumber
2

Saya ingin menambahkan sen saya ke jawaban teratas karena jika bahasa mendukung sesuatu seperti generator, bfs dapat dilakukan secara rekursif.

Untuk mulai dengan, jawaban @ Tanzelax berbunyi:

Breadth-first traversal secara tradisional menggunakan antrian, bukan tumpukan. Sifat antrian dan tumpukan cukup berlawanan, jadi mencoba menggunakan panggilan stack (yang merupakan tumpukan, maka nama) sebagai penyimpanan tambahan (antrian) cukup banyak ditakdirkan untuk gagal

Memang, stack pemanggilan fungsi biasa tidak akan berperilaku seperti stack normal. Tetapi fungsi generator akan menunda eksekusi fungsi sehingga memberi kita kesempatan untuk menghasilkan anak-anak node level berikutnya tanpa menggali keturunan node yang lebih dalam.

Kode berikut adalah bfs rekursif dengan Python.

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

Intuisi di sini adalah:

  1. bfs pertama akan mengembalikan root sebagai hasil pertama
  2. misalkan kita sudah memiliki urutan bfs, tingkat elemen berikutnya dalam bfs adalah anak langsung dari simpul sebelumnya dalam urutan bfs
  3. ulangi kedua prosedur di atas
Herrington Darkholme
sumber
Saya tidak tahu Python tapi saya pikir kode Anda diterjemahkan ke kode C # ini . Itu melakukan BFS traversal tetapi crash dengan pengecualian stackoverflow. Saya belum menemukan alasannya sejauh ini. Namun, saya memodifikasi algoritme sehingga berhenti (dan berkinerja lebih baik mungkin). Anda menemukan sampel kerja saya di sini .
Adam Simon
1

Saya harus mengimplementasikan heap traversal yang menghasilkan dalam urutan BFS. Ini sebenarnya bukan BFS tetapi menyelesaikan tugas yang sama.

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
sumber
2
Untuk pemirsa lain: ini adalah contoh penerapan pohon lengkap dalam array; Secara khusus, @Justin sedang melakukan traversal pre-order, di mana ia menyimpan nilai-nilai simpul (dalam urutan BFS) dalam sebuah array di indeks BFS yang sesuai. Ini memungkinkan fungsi panggilan untuk beralih secara linier melalui array, mencetak nilai dalam urutan BFS. Lihat deskripsi umum ini Catatan: fungsi panggilan harus menangani kasus pohon yang tidak lengkap.
bunkerdive
1

Biarkan v menjadi titik awal

Biarkan G menjadi grafik yang dipermasalahkan

Berikut ini adalah kode semu tanpa menggunakan antrian

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
sumber
Saya pikir ini mungkin terjebak dalam loop tak terbatas - simpul ditandai sebagai dikunjungi, tetapi mereka tidak pernah diuji untuk dikunjungi-sebelum sebelum berulang lagi.
Cuplikan ini lebih mirip dengan DFS daripada BFS
Dení
1

BFS untuk pohon biner (atau n-ary) dapat dilakukan secara rekursif tanpa antrian sebagai berikut (di sini di Jawa):

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

Contoh nomor pencetakan traversal 1-12 dalam urutan menaik:

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
sumber
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
sumber
0

Berikut adalah Implementasi JavaScript yang memalsukan Breadth First Traversal dengan Rekursi Depth First. Saya menyimpan nilai-nilai simpul di setiap kedalaman di dalam array, di dalam hash. Jika level sudah ada (kami memiliki tabrakan), jadi kami hanya mendorong ke array di level itu. Anda bisa menggunakan array bukan objek JavaScript juga karena level kami numerik dan dapat berfungsi sebagai indeks array. Anda dapat mengembalikan node, nilai, dikonversi ke Daftar Tertaut, atau apa pun yang Anda inginkan. Saya hanya mengembalikan nilai demi kesederhanaan.

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

Berikut ini adalah contoh Breadth First Traversal yang sebenarnya menggunakan pendekatan iteratif.

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
sumber
0

Berikut ini adalah kode saya untuk implementasi sepenuhnya rekursif dari pencarian luas-pertama dari grafik dua arah tanpa menggunakan loop dan antrian.

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
sumber
0

C # implementasi algoritma pencarian luas-rekursif pertama untuk pohon biner.

Visualisasi data pohon biner

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

Jika Anda ingin algoritma berfungsi tidak hanya dengan binary-tree tetapi dengan grafik yang dapat memiliki dua dan lebih banyak node yang menunjuk ke node lain yang sama, Anda harus menghindari siklus sendiri dengan memegang daftar node yang sudah dikunjungi. Implementasinya mungkin terlihat seperti ini.

Visualisasi data grafik

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
sumber
0

Saya telah membuat program menggunakan c ++ yang bekerja dalam grafik gabungan dan terpisah juga.

    #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
sumber