ชนิดของ edge ใน DFS tree (ค่ายวันที่ 11 มีนาคม 2551)
รุ่นแก้ไขเมื่อ 18:01, 11 มีนาคม 2551 โดย Cardcaptor (คุย | มีส่วนร่วม) (→แล้วจะรู้ได้อย่างไรว่า edge ไหน ชนิดไหน?)
หลังจาก 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 ค่าเวลาไว้ที่จุด ใดๆ ไว้สองค่า
