การค้นหาเชิงลึกครั้งแรกบนไดกราฟในโครงสร้างข้อมูล

การค้นหากราฟเชิงลึกในครั้งแรกมีความคล้ายคลึงกัน แต่สำหรับ Digraphs หรือกราฟกำกับ เราสามารถหาขอบบางประเภทได้ อัลกอริทึม DFS จะสร้างทรีที่เรียกว่า DFS tree ขอบมีสี่ประเภทที่เรียกว่า −

• ขอบต้นไม้ (T) − ขอบเหล่านั้นซึ่งมีอยู่ในแผนผัง DFS

• ขอบด้านหน้า (F) − ขนานกับชุดของขอบไม้ (จากหมายเลข DFS ที่เล็กกว่าไปจนถึงหมายเลข DFS ที่มากกว่า และหมายเลข DFS ที่เสร็จสมบูรณ์ที่ใหญ่กว่าไปจนถึงหมายเลข DFS ที่เสร็จสมบูรณ์ที่น้อยกว่า)

• ขอบด้านหลัง (B) − จากหมายเลข DFS ที่มากกว่าไปจนถึงหมายเลข DFS ที่เล็กกว่า และหมายเลข DFS ที่เสร็จสมบูรณ์ที่น้อยกว่าไปจนถึงหมายเลข DFS ที่สมบูรณ์กว่า

• ข้ามขอบ (C) − หมายเลข DFS ที่ใหญ่ขึ้นเป็นหมายเลข DFS ที่เล็กลง และหมายเลข DFS ที่เสร็จสมบูรณ์ที่ใหญ่กว่าจนถึงหมายเลขการเติม DFS ที่เล็กลง

สมมติว่าเรามีกราฟดังนี้ -

ตอนนี้เราจะดำเนินการ DFS โดยใช้ A เป็นยอดเริ่มต้น และใส่หมายเลข DFS และหมายเลขการเติม DFS ดังนั้นต้นไม้จะมีลักษณะดังนี้ -

ดังนั้น การข้ามผ่าน DFS คือ A, B, F, D, G, C, E

ขอบของต้นไม้คือ − T ={(A, B), (B, F), (F, D), (F, G), (A, C), (C, E)}

ขอบด้านหน้าคือ − F ={(A, G)}

ขอบด้านหลังคือ − B ={(G, B)}

ขอบตัดคือ −C ={(G, D)}