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

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$

algorithms graphs graph-traversal saadtaame
sumber

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

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

@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

. Bahkan lebih baik, jika

dan

memenuhi properti dan simpul

adalah yang terakhir diproses dalam

dan

adalah tempat pencarian dimulai pada

, kemudian menambahkan tepi jembatan

G = (V, E)

$G = (V,E)$

= v

$= v$

G_{1}

$G_1$

G_{2}

$G_2$

v_{1}

$v_1$

G_{1}

$G_1$

v_{2}

$v_2$

G_{2}

$G_2$

membuat grafik yang memenuhi properti. Mengganti

dengan

juga berfungsi saya pikir.

(v_{1}, v_{2})

$(v_1, v_2)$

v_{1}

$v_1$

v_{2}

$v_2$

saadtaame

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

. Berikut adalah proposisi saya: Diberikan grafik

, jika

sedemikian rupa sehingga

v

$v$

v

$v$

G = (V, E)

$G=(V,E)$

\forall x \in V

$\forall x \in V$

\exists y, z, w \in V

$\exists y,z,w \in V$

(y, x), (z, y), (x, w) \in E

$(y,x),(z,y),(x,w) \in E$ , lalu

(x, z) \in E ⟹

$(x,z) \in E \implies$ properti berlaku untuk

. Langkah selanjutnya adalah membuktikan atau menolak proposisi ini.

G

$G$

saadtaame

Jawaban:

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

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.