Perbedaan antara tepi silang dan tepi depan dalam DFT

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?

Wikipedia memiliki jawabannya:

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)

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.

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.

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

3. 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