Luas Pertama Vs Kedalaman Pertama

172

Ketika Melintasi Pohon / Grafik apa perbedaan antara Breadth First dan Depth pertama? Contoh pengkodean atau pseudocode akan bagus.

Ted Smith
sumber
6
Apakah Anda memeriksa wikipedia ( kedalaman dulu , lebarnya dulu )? Ada contoh kode di halaman itu, bersama dengan banyak gambar cantik.
rmeador
Saya memiliki pemikiran itu juga, tetapi kemudian contoh-contoh yang diberikan sedikit lebih baik daripada yang ditemukan di wikipedia ....
jonnybazookatone

Jawaban:

292

Kedua istilah ini membedakan antara dua cara berjalan pohon yang berbeda.

Mungkin paling mudah untuk menunjukkan perbedaannya. Pertimbangkan pohonnya:

    A
   / \
  B   C
 /   / \
D   E   F

Sebuah mendalam pertama traversal akan mengunjungi simpul dalam urutan ini

A, B, D, C, E, F

Perhatikan bahwa Anda berjalan jauh ke bawah satu kaki sebelum melanjutkan.

Sebuah luasnya pertama traversal akan mengunjungi node dalam urutan ini

A, B, C, D, E, F

Di sini kami bekerja sepanjang jalan di setiap level sebelum turun.

(Perhatikan bahwa ada beberapa ambiguitas dalam pesanan traversal, dan saya telah menipu untuk mempertahankan urutan "membaca" di setiap tingkat pohon. Dalam kedua kasus itu saya bisa mencapai B sebelum atau setelah C, dan juga saya bisa mendapatkan ke E sebelum atau sesudah F. Ini mungkin atau mungkin tidak masalah, tergantung pada aplikasi Anda ...)


Kedua jenis traversal dapat dicapai dengan kodesemu:

Store the root node in Container
While (there are nodes in Container)
   N = Get the "next" node from Container
   Store all the children of N in Container
   Do some work on N

Perbedaan antara dua perintah traversal terletak pada pilihan Container.

  • Untuk kedalaman, pertama gunakan tumpukan. (Implementasi rekursif menggunakan tumpukan panggilan ...)
  • Untuk luasnya dulu gunakan antrian.

Implementasi rekursif terlihat seperti

ProcessNode(Node)
   Work on the payload Node
   Foreach child of Node
      ProcessNode(child)
   /* Alternate time to work on the payload Node (see below) */

Rekursi berakhir ketika Anda mencapai simpul yang tidak memiliki anak, sehingga dijamin akan berakhir untuk grafik asiklik yang terbatas.


Pada titik ini, saya masih sedikit curang. Dengan sedikit kepintaran, Anda juga dapat mengerjakan node dalam urutan ini:

D, B, E, F, C, A

yang merupakan variasi dari kedalaman-pertama, di mana saya tidak melakukan pekerjaan di setiap node sampai saya berjalan kembali ke atas pohon. Namun saya telah mengunjungi node yang lebih tinggi dalam perjalanan untuk menemukan anak-anak mereka.

Traversal ini cukup alami dalam implementasi rekursif (gunakan baris "Waktu alternatif" di atas sebagai ganti baris "Work" pertama), dan tidak terlalu sulit jika Anda menggunakan stack eksplisit, tetapi saya akan membiarkannya sebagai latihan.

dmckee --- mantan kucing moderator
sumber
@ dmckee Terima kasih! Saya yakin maksud Anda adalah "Kerjakan muatan di Node," bukan?
batbrat
4
Mungkin perlu dicatat bahwa Anda dapat memodifikasi versi kedalaman-pertama untuk mendapatkan awalan ( A, B, D, C, E, F- yang pertama disajikan), infix ( D, B, A, E, C, F- digunakan untuk menyortir: tambahkan sebagai pohon AVL lalu baca infix) atau D, B, E, F, C, Atraversal postfix ( alternatif disajikan). Nama-nama diberikan oleh posisi di mana Anda memproses root. Perlu dicatat bahwa infiks hanya benar-benar masuk akal untuk pohon biner. @batbrat itu adalah nama-nama ... mengingat waktu sejak Anda bertanya, Anda mungkin sudah tahu.
Theraot
@Theraot terima kasih telah menambahkan itu! Ya, saya tahu tentang jenis-jenis traversal ini dan mengapa Infix hanya masuk akal untuk pohon biner.
batbrat
Bagaimana cara memutuskan solusi mana yang memiliki kompleksitas ruang atau waktu yang lebih baik?
IgorGanapolsky
1
@IgorGanapolsky Harus sama untuk keduanya pada prinsipnya (setelah semua, mereka pada dasarnya menggunakan kode yang sama). Pertanyaan yang lebih menarik adalah bagaimana mereka berdampak pada cache dan set kerja, tapi saya pikir itu akan tergantung pada morfologi pohon.
dmckee --- ex-moderator kitten
95

Memahami ketentuan:

Gambar ini harus memberi Anda ide tentang konteks di mana kata luas dan kedalaman digunakan.

Memahami Luas dan Kedalaman


Pencarian Kedalaman-Pertama:

Pencarian Kedalaman-Pertama

  • Algoritma pencarian Kedalaman-pertama bertindak seolah-olah ingin pergi sejauh mungkin dari titik awal.

  • Biasanya menggunakan a Stackuntuk mengingat ke mana ia harus pergi ketika mencapai jalan buntu.

  • Aturan untuk diikuti: Dorong verteks pertama A ke Stack

    1. Jika memungkinkan, kunjungi verteks yang belum dikunjungi yang berdekatan, tandai sebagai dikunjungi, dan dorong pada tumpukan.
    2. Jika Anda tidak dapat mengikuti Aturan 1, maka, jika mungkin, lepaskan simpul dari tumpukan.
    3. Jika Anda tidak dapat mengikuti Aturan 1 atau Aturan 2, Anda selesai.
  • Kode Java:

    public void searchDepthFirst() {
        // Begin at vertex 0 (A)
        vertexList[0].wasVisited = true;
        displayVertex(0);
        stack.push(0);
        while (!stack.isEmpty()) {
            int adjacentVertex = getAdjacentUnvisitedVertex(stack.peek());
            // If no such vertex
            if (adjacentVertex == -1) {
                stack.pop();
            } else {
                vertexList[adjacentVertex].wasVisited = true;
                // Do something
                stack.push(adjacentVertex);
            }
        }
        // Stack is empty, so we're done, reset flags
        for (int j = 0; j < nVerts; j++)
            vertexList[j].wasVisited = false;
    }
    
  • Aplikasi : Pencarian mendalam pertama kali sering digunakan dalam simulasi game (dan situasi seperti game di dunia nyata). Dalam gim biasa Anda dapat memilih salah satu dari beberapa tindakan yang mungkin. Setiap pilihan mengarah ke pilihan lebih lanjut, masing-masing mengarah ke pilihan lebih lanjut, dan seterusnya ke dalam grafik kemungkinan berbentuk pohon yang terus berkembang.


Pencarian Breadth-First:

Pencarian Luas Pertama

  • Algoritme pencarian luas pertama suka tetap sedekat mungkin ke titik awal.
  • Pencarian semacam ini umumnya diimplementasikan menggunakan a Queue.
  • Aturan yang harus diikuti: Jadikan titik awal A titik saat ini
    1. Kunjungi vertex yang belum dikunjungi berikutnya (jika ada) yang berdekatan dengan vertex saat ini, tandai, dan masukkan ke dalam antrian.
    2. Jika Anda tidak dapat menjalankan Aturan 1 karena tidak ada lagi simpul yang belum dikunjungi, hapus simpul dari antrian (jika mungkin) dan jadikan sebagai simpul saat ini.
    3. Jika Anda tidak dapat menjalankan Aturan 2 karena antriannya kosong, Anda selesai.
  • Kode Java:

    public void searchBreadthFirst() {
        vertexList[0].wasVisited = true;
        displayVertex(0);
        queue.insert(0);
        int v2;
        while (!queue.isEmpty()) {
            int v1 = queue.remove();
            // Until it has no unvisited neighbors, get one
            while ((v2 = getAdjUnvisitedVertex(v1)) != -1) {
                vertexList[v2].wasVisited = true;
                // Do something
                queue.insert(v2);
            }
        }
        // Queue is empty, so we're done, reset flags
        for (int j = 0; j < nVerts; j++) 
            vertexList[j].wasVisited = false;
    }
    
  • Aplikasi : Pencarian Breadth-first pertama-tama menemukan semua simpul yang satu ujung dari titik awal, lalu semua simpul yang berjarak dua tepi, dan seterusnya. Ini berguna jika Anda mencoba menemukan jalur terpendek dari titik awal ke titik tertentu.

Semoga itu cukup untuk memahami pencarian Breadth-First dan Depth-First. Untuk bacaan lebih lanjut saya akan merekomendasikan bab Grafik dari buku struktur data yang sangat baik oleh Robert Lafore.

Yogesh Umesh Vaity
sumber
6
Jika saya memiliki sepuluh suara lagi dengan benar, saya akan melakukannya.
snr
@ snr Anda bisa memberikan hadiah;)
Snow
@Sekarang jika Anda memberi tahu arahannya, saya bisa. Saya tidak tahu caranya.
snr
Terima kasih @ nn, saya sangat senang menerima hadiah pertama saya. Saya sangat menghargai.
Yogesh Umesh Vaity
1
Terima kasih @Snow, saya senang kalian menemukan jawaban saya berguna.
Yogesh Umesh Vaity
4

Diberikan pohon biner ini:

masukkan deskripsi gambar di sini

Breadth First Traversal:
Melintasi setiap level dari kiri ke kanan.

"Aku G, anak-anakku D dan aku, cucuku adalah B, E, H dan K, cucu mereka adalah A, C, F"

- Level 1: G 
- Level 2: D, I 
- Level 3: B, E, H, K 
- Level 4: A, C, F

Order Searched: G, D, I, B, E, H, K, A, C, F

Depth First Traversal:
Traversal tidak dilakukan ACROSS seluruh level sekaligus. Sebagai gantinya, penyelaman traversal ke DEPTH (dari akar ke daun) dari pohon terlebih dahulu. Namun, ini sedikit lebih kompleks daripada hanya naik turun.

Ada tiga metode:

1) PREORDER: ROOT, LEFT, RIGHT.
You need to think of this as a recursive process:  
Grab the Root. (G)  
Then Check the Left. (It's a tree)  
Grab the Root of the Left. (D)  
Then Check the Left of D. (It's a tree)  
Grab the Root of the Left (B)  
Then Check the Left of B. (A)  
Check the Right of B. (C, and it's a leaf node. Finish B tree. Continue D tree)  
Check the Right of D. (It's a tree)  
Grab the Root. (E)  
Check the Left of E. (Nothing)  
Check the Right of E. (F, Finish D Tree. Move back to G Tree)  
Check the Right of G. (It's a tree)  
Grab the Root of I Tree. (I)  
Check the Left. (H, it's a leaf.)  
Check the Right. (K, it's a leaf. Finish G tree)  
DONE: G, D, B, A, C, E, F, I, H, K  

2) INORDER: LEFT, ROOT, RIGHT
Where the root is "in" or between the left and right child node.  
Check the Left of the G Tree. (It's a D Tree)  
Check the Left of the D Tree. (It's a B Tree)  
Check the Left of the B Tree. (A)  
Check the Root of the B Tree (B)  
Check the Right of the B Tree (C, finished B Tree!)  
Check the Right of the D Tree (It's a E Tree)  
Check the Left of the E Tree. (Nothing)  
Check the Right of the E Tree. (F, it's a leaf. Finish E Tree. Finish D Tree)...  
Onwards until...   
DONE: A, B, C, D, E, F, G, H, I, K  

3) POSTORDER: 
LEFT, RIGHT, ROOT  
DONE: A, C, B, F, E, D, H, K, I, G

Penggunaan (alias, mengapa kita peduli):
Saya benar-benar menikmati penjelasan Quora sederhana ini tentang metode Traversal Kedalaman Pertama dan bagaimana mereka biasa digunakan:
"In-Order Traversal akan mencetak nilai [agar BST (pohon pencarian biner)] "
" Travers pre-order digunakan untuk membuat salinan [pohon pencarian biner]. "
"Travers postorder digunakan untuk menghapus [pohon pencarian biner]."
https://www.quora.com/What-is-the-use-of-pre-order-and-post-order-traversal-of-binary-trees-in-computing

msyinmei
sumber
2

Saya pikir akan menarik untuk menulis keduanya dengan cara yang hanya dengan mengganti beberapa baris kode akan memberikan Anda satu algoritma atau yang lain, sehingga Anda akan melihat bahwa dillema Anda tidak begitu kuat seperti yang terlihat pada awalnya. .

Saya pribadi menyukai interpretasi BFS sebagai membanjiri lanskap: daerah dataran rendah akan dibanjiri terlebih dahulu, dan baru kemudian daerah dataran tinggi akan mengikuti. Jika Anda membayangkan ketinggian lanskap sebagai isoline seperti yang kita lihat dalam buku-buku geografi, mudah untuk melihat bahwa BFS mengisi semua area di bawah isoline yang sama pada saat yang sama, seperti halnya dengan fisika. Dengan demikian, menafsirkan ketinggian sebagai jarak atau biaya skala memberikan ide algoritma yang cukup intuitif.

Dengan pemikiran ini, Anda dapat dengan mudah menyesuaikan ide di balik pencarian pertama yang luas untuk menemukan pohon rentang minimum dengan mudah, jalur terpendek, dan juga banyak algoritma minimisasi lainnya.

Saya belum melihat interpretasi intuitif dari DFS (hanya yang standar tentang labirin, tetapi tidak sekuat BFS dan banjir), jadi bagi saya tampaknya BFS tampaknya berkorelasi lebih baik dengan fenomena fisik seperti dijelaskan di atas, sementara DFS berkorelasi lebih baik dengan pilihan dillema pada sistem rasional (yaitu orang atau komputer yang memutuskan untuk melakukan permainan catur atau keluar dari labirin).

Jadi, bagi saya perbedaan antara kebohongan di mana fenomena alam paling cocok dengan model propagasi mereka (transversing) dalam kehidupan nyata.

pengguna5193682
sumber
1
Anda dapat menerapkannya dengan algoritma yang sama, cukup gunakan tumpukan untuk DFS dan antrian untuk BFS. Masalah dengan BFS adalah Anda harus melacak semua node yang terlihat sejauh ini. DFS dalam fisika .. Saya membayangkan alam semesta alternatif dan Anda ingin satu dengan kehidupan, semua anak-anak dari akar, adalah poni besar yang berbeda dan Anda pergi sampai ke kematian alam semesta, tidak ada kehidupan? Anda kembali ke bifurkasi terakhir dan mencoba belokan lain, sampai semua habis dan Anda pergi ke big-bang berikutnya, menetapkan hukum fisik baru untuk alam semesta baru. sangat intuitif. masalah yang baik adalah menemukan jalan dengan kuda di papan catur.
juanmf