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