ชนิดของ edge ใน DFS tree (ค่ายวันที่ 11 มีนาคม 2551)
รุ่นแก้ไขเมื่อ 18:11, 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 ค่าเวลาไว้ที่จุด ใดๆ ไว้สองค่า หนึ่งคือเวลา discovery time (เขียนแทนด้วย ) และหนึ่งคือเวลา finish time (เขียนแทนด้วน ) โดย
![{\displaystyle d[v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2f7ef407a311eccc99fb0d4cd24faacde606c4b)
![{\displaystyle f[v]\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/acbb1e064be58a4857496d8d3e3c5ad41f2c0307)
- คือเวลาที่ DFS เดินมาถึง ครั้งแรก
- คือเวลาที่ DFS สำรวจ และ vertex ที่ไปถึงจากมันได้จนหมดแล้ว กำลังจะ backtrack กลับออกไป
การบันทึกค่าเวลาทั้งสองสามารถทำได้ตาม pseudocode ต่อไปนี้: ให้มีตัวแปล global ชื่อ time แทนเวลาของระบบ
function DFS(v)
{
time = time + 1
d[v] = time
for edge (v,w) ทุกๆ edge
if w ยังไม่ีเคยถูก DFS เดินไปถึง
DFS(w)
time = time + 1
f[v] = time
}
ค่า และ มีคุณสมบัติที่สำคัญเรียกว่า คุณสมบัติวงเล็บ ดังต่อไปนี้
