การค้นหาแบบทึกก่อน (DFS) บน Digraph ในโครงสร้างข้อมูล

ประเภทของเส้นขอบใน DFS บน Digraph

DFS สร้างต้นไม้ที่เรียกว่า DFS Tree มีเส้นขอบ 4 ประเภท:

• Tree Edge (T): เส้นขอบที่อยู่ใน DFS Tree
• Forward Edge (F): ขนานกับชุด Tree Edges (DFS number น้อยไปมาก, Completion number มากไปน้อย)
• Backward Edge (B): จาก DFS number มากไปน้อย และ Completion number น้อยไปมาก
• Cross Edge (C): DFS number มากไปน้อย และ Completion number มากไปน้อย

ตัวอย่างกราฟ

DFS Tree และการจัดประเภทเส้นขอบ

เริ่มจากโหนด A ใส่ DFS Number และ Completion Number:

DFS Traversal: A, B, F, D, G, C, E

• Tree Edges: T = {(A,B), (B,F), (F,D), (F,G), (A,C), (C,E)}
• Forward Edges: F = {(A,G)}
• Backward Edges: B = {(G,B)}
• Cross Edges: C = {(G,D)}