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

แล้วจะรู้ได้อย่างไรว่า edge ไหน ชนิดไหน?

เราจะใช้สมบัติของ discovery time และ finish time ของ vertex ใน DFS forest มาช่วย

เวลาเราทำ DFS เรา save ค่าเวลาไว้ที่จุด $v\,$ ใดๆ ไว้สองค่า หนึ่งคือเวลา discovery time (เขียนแทนด้วย $d[v]\,$) และหนึ่งคือเวลา finish time (เขียนแทนด้วน $f[v]\,$) โดย

• $d[v]\,$ คือเวลาที่ DFS เดินมาถึง $v\,$ ครั้งแรก
• $f[v]\,$ คือเวลาที่ DFS สำรวจ $v\,$ และ vertex ที่ไปถึงจากมันได้จนหมดแล้ว กำลังจะ backtrack กลับออกไป

การบันทึกค่าเวลาทั้งสองสามารถทำได้ตาม pseudocode ต่อไปนี้: ให้มีตัวแปล global ชื่อ time แทนเวลาของระบบ

function DFS(v)
{
  time = time + 1
  d[v] = time
  
  สำหรับ edge (v,w) ทุกๆ edge
    ถ้า w ยังไม่ีเคยถูก DFS เดินไปถึง
      DFS(w)
  
  time = time + 1
  f[v] = time
}