Apakah Anda mendapatkan DFS jika Anda mengubah antrian ke tumpukan dalam implementasi BFS?

Ini adalah pseudocode standar untuk pencarian pertama luasnya:

{ seen(x) is false for all x at this point }
push(q, x0)
seen(x0) := true
while (!empty(q))
  x := pop(q)
  visit(x)
  for each y reachable from x by one edge
    if not seen(y)
      push(q, y)
      seen(y) := true

Di sini pushdan popdianggap sebagai operasi antrian. Tetapi bagaimana jika mereka adalah operasi stack? Apakah algoritma yang dihasilkan mengunjungi simpul dalam urutan pertama?

Jika Anda memilih komentar "ini sepele", saya akan meminta Anda untuk menjelaskan mengapa itu sepele. Saya menemukan masalahnya cukup rumit.

algorithms graphs rgrig
sumber

Saya telah melihat siswa bergumul dengan ini, jadi saya tidak berpikir itu terlalu sederhana. Namun, apa yang lebih dari "Ya" atau "Tidak" yang seharusnya berisi jawaban? Granularitas yang diinginkan tidak jelas dari pertanyaan.

Raphael

"Ya" akan datang dengan argumen yang meyakinkan; "Tidak" akan datang dengan contoh tandingan. Tetapi ada jawaban yang lebih baik daripada ya / tidak begitu Anda memahami apa yang terjadi ...

rgrig

@ Jo, Dave: silakan lihat diskusi meta berikutnya

Gilles 'SO- stop being evil'

Dimungkinkan untuk menulis pseudo-code sehingga hanya dengan mengubah popke stack atau operasi antrian, kita mendapatkan dfs atau bfs. Juga mudah untuk menulis pseudo-code yang pertama kali muncul bahwa ini benar, tetapi tidak. ics.uci.edu//~eppstein/161/960215.html adalah referensi yang relevan.

Joe

Jawaban:

Tidak, ini tidak sama dengan DFS.

Perhatikan grafiknya

masukkan deskripsi gambar di sini

Jika Anda mendorong node dalam urutan kanan ke kiri, algoritma memberi Anda traversal:

$A, B , E, C , D$

sementara DFS akan mengharapkannya

$A,B,E,D,C$

Masalah terjadi karena Anda menandainya seperti yang terlihat pada saat mendorong, bukan pada saat berkunjung. Seperti yang ditunjukkan dalam komentar, jika Anda menandai pada saat berkunjung, persyaratan ruang Anda mungkin naik ke daripada . $\Theta(V+E)$ $\mathcal{O}(V)$

Saya setuju, masalahnya tidak sepele.

Aryabhata
sumber

Ini mengasumsikan bahwa daftar adjacency memiliki beberapa urutan spesifik tetap. Paling tidak dalam matematika, seseorang memandangnya sebagai himpunan, dan grafik memiliki beberapa traversal urutan kedalaman, tergantung pada bagaimana Anda bisa mengulangi anak-anak. (Bayangkan menggunakan hash untuk anak-anak.) Dalam hal itu, ABECD masih merupakan urutan pertama. Penanya bertanya-tanya apakah ada contoh tandingan bahkan dalam pengaturan ini. (Memang, di sinilah mulai menjadi rumit.)

rgrig

D

$D$

E

$E$

D

$D$

@Arybhata: Oh, maaf, saya tidak tahu mengapa saya berasumsi bahwa Anda bermaksud agar ujungnya diarahkan dan mengarah ke bawah. Mereka tidak diarahkan, jadi Anda benar: Ini adalah contoh tandingan bahkan untuk apa yang saya katakan dalam komentar. (Ini aneh: Saya harus salah mengeja pegangan Anda, sehingga tidak bisa dihapus oleh SE.)

rgrig