ดูต้นฉบับสำหรับ ชนิดของ edge ใน DFS tree (ค่ายวันที่ 11 มีนาคม 2551)

หลังจาก DFS บท directed graph เราสามารถแบ่ง edge ในกราฟออกได้เป็น 4 ประเภท ได้แก่
* '''Tree edge''' คือ edge ที่อยู่บน DFS tree ที่ได้จากการทำ DFS
* '''Back edge''' คือ edge ที่พุ่งออกจาก vertex ไปหาบรรพบุรุษของมันใน DFS tree
* '''Forward edge''' คือ edge ที่พุ่งออกจาก vertex ไปหาลูกหลานของมันใน DFS tree
* '''Cross edge''' คือ edge อื่นๆ ที่ไม่เข้าพวกทั้งสามข้างต้น
ยกตัวอย่างเช่น ในกราฟต่อไปนี้

[[ภาพ:Dfs-graph-01.JPG|500px]]

ถ้าเราทำ DFS โดยเดินผ่าน vertex ตามลำดับต่อไปนี้: s, z, y, x, w, t, v, u แล้ว edge ต่างๆ ในกราฟจะมีประเภทตามรูปข้างล่างนี้

[[ภาพ:Dfs-graph-02.JPG|500px]]

== แล้วจะรู้ได้อย่างไรว่า edge ไหนประเภทไหน? ==
=== Discover Time และ Finish Time ===
เราจะใช้สมบัติของ discovery time และ finish time ของ vertex ใน DFS forest มาช่วย

เวลาเราทำ DFS เรา save ค่าเวลาไว้ที่จุด <math>v\,</math> ใดๆ ไว้สองค่า หนึ่งคือเวลา ''discovery time'' (เขียนแทนด้วย <math> d[v]\,</math>) และหนึ่งคือเวลา ''finish time'' (เขียนแทนด้วน <math>f[v]\,</math>) โดย
* <math>d[v]\,</math> คือเวลาที่ DFS เดินมาถึง <math>v\,</math> ครั้งแรก
* <math>f[v]\,</math> คือเวลาที่ DFS สำรวจ <math>v\,</math> และ vertex ที่ไปถึงจากมันได้จนหมดแล้ว กำลังจะ backtrack กลับออกไป

การบันทึกค่าเวลาทั้งสองสามารถทำได้ตาม pseudocode ต่อไปนี้: ให้มีตัวแปล global ชื่อ time แทนเวลาของระบบ
 function DFS(v)
 {
     time = time + 1
     d[v] = time
     visited[v] = true
   
     for edge (v,w) ทุกๆ edge
         if visited[w] == false
             DFS(w)
   
     time = time + 1
     f[v] = time
 }
ยกตัวอย่างเช่น ถ้าเรานำอัลกอริทึมข้างต้นไปรันกับกราฟข้างบน เราจะได้ค่า <math>d[v]\,</math> และ <math>f[v]\,</math> ของแต่ละ vertex ดังต่อไปนี้ (เราเขียน <math>d[v]/f[v]\,</math> ไว้ตรงกลาง vertex แต่ละ vertex)

[[ภาพ:Dfs-graph-03.JPG|500px]]

=== สมบัติวงเล็บ ===
ค่า <math>d[v]\,</math> และ <math>f[v]\,</math> มีสมบัติที่สำคัญเรียกว่า '''สมบัติวงเล็บ''' ดังต่อไปนี้
<blockquote>
ถ้า <math>u\,</math> และ <math>v\,</math> เป็น vertex สอง vertex ใดๆ ในกราฟแล้ว ภายในข้อเท็จจริงสามข้อต่อไปนี้ จะมีข้อเท็จจริงข้อหนึ่งเป็นจริง และมันจะเป็นจริงเพียงข้อเดียวเท่านั้น
# <math>d[u] < d[v] < f[v] < f[u]\,</math>
# <math>d[v] < d[u] < f[u] < f[v]\,</math>
# ช่วง <math>[d[u], f[u]]\,</math> และ <math>[d[v], f[v]]\,</math> ไม่มีสมาชิกร่วมกันเลย
</blockquote>
กรณีที่ 1 ตรงกับเหตุการณ์ที่ <math>u\,</math> เป็นบรรพบุรุษของ <math>v\,</math> ใน DFS tree กรณีที่ 2 ตรงกับเหตุการณ์ที่ <math>v\,</math> เป็นบรรพบุรุษของ <math>v\,</math> ส่วนกรณีที่ 3 ตรงกับเหตุการณ์ที่ไม่มีใครเป็นบรรพบุรุษใคร

=== แบ่งประเภทของ edge ===
สำหรับ edge <math>e = (u,v)\,</math> ใดๆ เราสามารถใช้สมบัติวงเล็บข้างต้นในการจำแนกประเภทของมันได้
* ถ้า <math>d[u] < d[v] < f[v] < f[u]\,</math> แสดงว่า <math>u\,</math> เป็นบรรพบุรุษของ <math>v\,</math> ฉะนั้น <math>e\,</math> ต้องเป็น tree edge หรือ forward edge
* ถ้า <math>d[v] < d[u] < f[u] < f[v]\,</math> แสดงว่า <math>v\,</math> เป็นบรรพบุรุษของ <math>u\,</math> ฉะนั้น <math>e\,</math> ต้องเป็น back edge
* ถ้า <math>[d[u], f[u]]\,</math> และ <math>[d[v], f[v]]\,</math> แสดงว่าไม่มีใครเป็นบรรพบุรุษใคร ดังนั้น <math>e\,</math> ต้องเป็น cross edge
ปัญหาที่เหลือคือ ในกรณีแรก เราจะแยกได้อย่างไรว่า edge ไหนเป็น tree edge และ edge ไหนเป็น forward edge? คำตอบคือเวลาทำ DFS ก็ให้ mark เอาไว้ว่า edge ไหนบ้างคือ tree edge แล้วก็ให้ไปเช็คที่ mark นั้นเอา

== ชนิดของ edge ใน undirected graph ==
หากเราทำ DFS บน undirected graph เราสามารถแบ่ง edge ออกได้เป็นสองชนิดเท่านั้นคือ '''tree edge และ back edge'''

ทำไมถึงไม่มี forward edge หรือ cross edge เลย? ลองคิดดูว่าถ้ามี cross edge จะเกิดอะไรขึ้น

[[ภาพ:cross-edge-contradiction.JPG|300px]]

จากรูปข้างบน สมมติว่า DFS เดินทางจาก root ไปถึง x ก่อนแล้วค่อยไป y โดยเมื่อไปถึง y แล้วมันจึงเห็น x 

หมายความว่า DFS(x) จะต้อง exit ก่อนที่ DFS(y) จะถูกเรียก

แต่นี่เป็นไปไม่ได้ เพราะถ้า DFS(x) ถูกเรียกแล้ว มันจะตรวจดู edge ทุก edge ที่ต่อกับ x ดังนั้นมันต้องเจอ y โดยผ่าน cross edge ที่เราคิดว่ามันมี ก่อนแล้วจึงเรียก DFS(y) ก่อน DFS(x) จะ exit ออกมา เกิดข้อขัดแย้ง 

ดังนั้นจึงไม่มี cross edge ใน undirected graph

เราสามารถแสดงได้ว่าใน undirected graph ไม่มี forward edge ได้ด้วยการให้เหตุผลเดียวกัน