Grafik yang menyebabkan DFS dan BFS memproses node dalam urutan yang sama persis

11

Untuk beberapa grafik, algoritma pencarian DFS dan BFS memproses simpul dalam urutan yang sama persis asalkan keduanya dimulai pada simpul yang sama. Dua contoh adalah grafik yang merupakan jalur dan grafik yang berbentuk bintang (pohon kedalaman dengan jumlah anak yang berubah-ubah). Apakah ada cara untuk mengelompokkan grafik yang memenuhi properti ini?1

saadtaame
sumber
6
Perhatikan bahwa dalam kedua kasus ini hanya berfungsi jika Anda mulai pada beberapa node tertentu. Jika Anda memilih simpul pusat di jalur panjang, misalnya, Anda akan mendapatkan kembali urutan berbeda dari DFS dan BFS.
templatetypedef
1
Apakah ada kemungkinan menarik selain bintang atau jalur? Pada pandangan pertama akan terlihat bahwa jika Anda memiliki simpul dengan saudara kandung dan seorang anak maka Anda segera mendapatkan traversal yang berbeda, sehingga tidak ada simpul yang memiliki anak (terlepas dari root) dan Anda mendapatkan bintang, atau tidak ada simpul memiliki saudara kandung dan Anda mendapatkan jalan. Saya kira klik juga berfungsi, tetapi memiliki bintang dan jalur yang tertanam.
Luke Mathieson
2
@LukeMathieson Saya sedang memikirkan sebuah bintang dengan anak paling kanan menjadi akar dari bintang lain. Saya kira itu akan berhasil juga. Kita bahkan dapat membuat pernyataan umum: jika memenuhi properti ketika pencarian dimulai pada simpul v∈V, maka demikian pula bintang yang anak paling kanan = v . Bahkan lebih baik, jika G 1 dan G 2 memenuhi properti dan simpul v 1 adalah yang terakhir diproses dalam G 1 dan v 2 adalah tempat pencarian dimulai pada G 2 , kemudian menambahkan tepi jembatan ( vG=(V,E)=vG1G2v1G1v2G2 membuat grafik yang memenuhi properti. Mengganti v 1 dengan v 2 juga berfungsi saya pikir. (v1,v2)v1v2
saadtaame
2
Poin bagus, jadi ada semacam komposisi rekursif kanan di mana Anda bisa mengidentifikasi daun kanan grafik pertama dengan akar yang kedua.
Luke Mathieson
@LukeMathieson Sepertinya Anda dapat memperbaiki kasus di mana simpul memiliki saudara dan anak dengan menambahkan tepi antara anak itu dan induk dari v . Berikut adalah proposisi saya: Diberikan grafik G = ( V , E ) . x V , jika y , z , w V sedemikian rupa sehingga ( y , x ) , ( z , y ) , ( x , w ) EvvG=(V,E)xVy,z,wV(y,x),(z,y),(x,w)E, lalu (x,z)Eproperti berlaku untuk . Langkah selanjutnya adalah membuktikan atau menolak proposisi ini. G
saadtaame

Jawaban:

6

Asumsikan BFS dan dfs kami memiliki aturan untuk memulai dari node tertentu dan dalam setiap dua arah mereka pertama kali mengunjungi node dengan derajat terendah:

DFS-BFS

mulai dari simpul hitam paling kiri, kemudian (BFS dan DFS) adalah kunjungan simpul merah paling kiri, lalu mereka akan mengunjungi simpul hitam berikutnya, dan seterusnya, untuk membuatnya lebih umum, Anda bisa menambahkan beberapa jalur di antara segitiga, atau menambahkan bintang setelah menyelesaikan segitiga ...


sumber
Itu benar berdasarkan asumsi Anda. Anda benar-benar mengangkat poin yang baik; kita harus menentukan dalam urutan apa node ditambahkan ke agenda (tumpukan atau antrian) ketika dihadapkan dengan pilihan.
saadtaame
Dengan mengingat bahwa LIFO dan FIFO untuk penjadwalan masing-masing menghasilkan DFS dan BFS, orang mungkin berpendapat bahwa penjadwalan seperti ini (di mana penjadwalan mungkin tidak berupa tumpukan atau antrian) bukanlah pencarian pertama maupun pertama - meskipun Anda dapat dalam beberapa kasus menggambarkan kecenderungannya menyerupai satu atau yang lain.
Niel de Beaudrap
1
Saya pikir itu bisa diimplementasikan dalam hal tumpukan atau antrian. Itu tidak mengubah bagaimana hal dilepas (LIFO atau FIFO), itu mengubah urutan anak-anak ditambahkan (dalam hal ini, tingkat terendah terlebih dahulu).
SamM
@NieldeBeaudrap sebenarnya ini hanya struktur untuk menunjukkan bahwa di suatu tempat kedua cara itu sama.