Perbedaan antara tepi silang dan tepi depan dalam DFT

11

Di pohon kedalaman pertama, ada tepi menentukan pohon (yaitu tepi yang digunakan dalam traversal).

Ada beberapa tepi sisa yang menghubungkan beberapa node lainnya. Apa perbedaan antara tepi silang dan tepi depan?

Dari wikipedia:

Berdasarkan spanning tree ini, tepi grafik asli dapat dibagi menjadi tiga kelas: tepi depan, yang menunjuk dari simpul pohon ke salah satu keturunannya, tepi belakang, yang menunjuk dari sebuah simpul ke salah satu leluhurnya, dan lintas tepi, yang tidak melakukan keduanya. Kadang-kadang tepi pohon, tepi yang termasuk ke pohon spanning itu sendiri, diklasifikasikan secara terpisah dari tepi depan. Jika grafik asli tidak diarahkan maka semua tepi adalah tepi pohon atau tepi belakang.

Bukankah tepi yang tidak digunakan dalam traversal yang menunjuk dari satu simpul ke simpul lainnya membentuk hubungan orangtua-anak?

soando
sumber
Terkait: cs.stackexchange.com/questions/99988/… berupaya membuat algoritma yang, untuk grafik berarah, akan lebih memilih untuk membuat tepi maju, daripada tepi silang, selama pencarian kedalaman-pertama.
pfalcon

Jawaban:

23

Wikipedia memiliki jawabannya:

masukkan deskripsi gambar di sini

Semua jenis tepi muncul di gambar ini. Lacak DFS pada grafik ini (node ​​dieksplorasi dalam urutan numerik), dan lihat di mana intuisi Anda gagal.


Ini akan menjelaskan diagram: -

Tepi depan: (u, v), di mana v adalah turunan dari Anda, tetapi bukan tepi pohon. Ini adalah tepi non-pohon yang menghubungkan titik ke turunan dalam pohon-DFS.

Cross edge: tepi lainnya. Dapat pergi di antara simpul dalam pohon kedalaman-pertama yang sama atau di pohon kedalaman-pertama yang berbeda. (awam)
Ini adalah tepi lain dalam grafik G. Ini menghubungkan simpul dalam dua pohon DFS yang berbeda atau dua simpul dalam pohon DFS yang sama yang tidak merupakan nenek moyang dari yang lain. (formal)

Yuval Filmus
sumber
Mengapa tidak mungkin bagi 6 orang untuk dilalui lebih dulu (sisi kanan lebih dulu)? Jika itu terjadi, apa yang akan disebut tepi 2-> 3?
soandos
@soando, saya sarankan Anda meluangkan waktu sendiri untuk melacak algoritma. Dengan asumsi para Wikipedian tidak melakukan kesalahan, gambar tersebut menggambarkan proses DFS yang bonafid pada grafik ini, dan ada cara untuk menyesuaikan algoritme ke dalam jejak ini. Jenis tepi dijelaskan dengan cukup jelas di Wikipedia, dan Anda juga dapat melihat contoh ini.
Yuval Filmus
Saya mengerti bahwa ini adalah cara yang valid untuk melakukan DFS. Saya hanya bertanya bagaimana jika itu dilakukan dengan cara lain.
soandos
Maka hasilnya akan berbeda. Maaf, Anda harus menyelesaikannya sendiri.
Yuval Filmus
2
@soando Secara umum, mungkin ada banyak DFS traversal. Gagasan yang digunakan di sini relatif terhadap satu traversal yang diberikan dan akan berbeda untuk beberapa traversal.
Raphael
9

Traversal DFS dalam grafik yang tidak diarahkan tidak akan meninggalkan tepi silang karena semua tepi yang terjadi pada titik dieksplorasi.

Namun, dalam grafik terarah, Anda mungkin menemukan tepi yang mengarah ke titik yang telah ditemukan sebelumnya sehingga titik itu bukan leluhur atau keturunan dari titik saat ini. Tepi seperti itu disebut tepi silang.

Apoorv Gupta
sumber
Aporov, Terima kasih atas tanggapannya. Bagi saya masih terlihat bahwa ketika Anda sampai ke titik 6 di DFS seperti yang digambarkan dalam Wikipedia, Anda memiliki tiga sisi untuk dilintasi dari 6. Pada titik itu, titik 6 adalah "saat ini". Akhirnya Anda akan melintasi tepi ke puncak 3. Meskipun 3 telah dikunjungi, namun karena ada tepi dari 6 ke 3, maka 3 adalah turunan dari titik "saat ini" 6. Jika demikian, itu melanggar definisi tepi silang. Pasti ada sesuatu yang lebih untuk definisi yang tidak dibuat sangat eksplisit.
Faktanya, DFS hanya berisi tepi pohon untuk tepi belakang (Intro ke Algoritma Thm. 22.10).
jrhee17
2

Dalam traversal DFS, node selesai begitu semua anak mereka selesai. Jika Anda menandai waktu temukan dan selesai untuk setiap node selama traversal, maka Anda dapat memeriksa untuk melihat apakah sebuah node adalah turunan dengan membandingkan waktu mulai dan akhir. Faktanya setiap traversal DFS akan mempartisi tepinya sesuai dengan aturan berikut.

Biarkan d [simpul] menjadi waktu penemuan simpul, juga biarkan f [simpul] menjadi waktu selesai.

Teorema Parenthesis Untuk semua u, v, tepat salah satu dari yang berikut ini berlaku:
1. d [u] <f [u] <d [v] <f [v] atau d [v] <f [v] <d [u ] <f [u] dan tak satu pun dari u dan v adalah turunan dari yang lain.

  1. d [u] <d [v] <f [v] <f [u] dan v adalah turunan dari u.

  2. d [v] <d [u] <f [u] <f [v] dan kamu adalah turunan dari v.

Jadi, d [u] <d [v] <f [u] <f [v] tidak dapat terjadi.
Seperti tanda kurung: () [], ([]), dan [()] OK tapi ([)] dan [(]) tidak OK.

Misalnya, perhatikan grafik dengan tepian:
A -> B
A -> C
B -> C

Biarkan urutan kunjungan diwakili oleh string label node, di mana "ABCCBA" berarti A -> B -> C (selesai) B (selesai) A (selesai), mirip dengan ((())).

Jadi "ACCBBA" bisa menjadi model untuk "(() ())".

Contoh:
"CCABBA": Maka A -> C adalah tepi melintang, karena CC tidak berada di dalam A.
"ABCCBA": Lalu A -> C adalah tepi ke depan (keturunan tidak langsung).
"ACCBBA": Lalu A -> C adalah tepi pohon (keturunan langsung).

Sumber:
CLRS:
https://mitpress.mit.edu/books/introduction-algorithms
Lecure Notes http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/GraphAlgor/depthSearch.htm

Chris Hafley
sumber