โครงสร้างข้อมูล - การข้ามผ่านครั้งแรกเชิงลึก
อัลกอริธึม Depth First Search (DFS) สำรวจกราฟในการเคลื่อนที่เชิงลึกและใช้สแต็กเพื่อจำเพื่อให้ได้จุดยอดถัดไปเพื่อเริ่มการค้นหาเมื่อมีทางตันเกิดขึ้นในการวนซ้ำใด ๆ
ดังตัวอย่างที่ให้ไว้ข้างต้นอัลกอริทึม DFS จะข้ามจาก S ไป A ไป D ไป G ถึง E ไป B ก่อนจากนั้นไปที่ F และสุดท้ายถึง C มันใช้กฎต่อไปนี้
Rule 1- เยี่ยมชมจุดยอดที่ไม่ได้เข้าชมที่อยู่ติดกัน ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงมัน ดันเข้าไปในกอง
Rule 2- หากไม่พบจุดยอดที่อยู่ติดกันให้เปิดจุดยอดจากสแต็ก (จุดยอดทั้งหมดจะปรากฏขึ้นจากสแต็กซึ่งไม่มีจุดยอดที่อยู่ติดกัน)
Rule 3 - ทำซ้ำกฎ 1 และกฎ 2 จนกว่าสแต็กจะว่างเปล่า
ขั้นตอน | ข้ามผ่าน | คำอธิบาย |
---|---|---|
1 |
|
เริ่มต้นสแต็ก |
2 |
|
เครื่องหมาย Sตามที่เยี่ยมชมและวางลงในสแต็ก สำรวจโหนดที่อยู่ติดกันที่ไม่ได้เข้าชมจากS. เรามีสามโหนดและเราสามารถเลือกโหนดใดก็ได้ สำหรับตัวอย่างนี้เราจะนำโหนดตามลำดับตัวอักษร |
3 |
|
เครื่องหมาย Aตามที่เยี่ยมชมและวางลงในสแต็ก สำรวจโหนดที่อยู่ติดกันที่ไม่ได้มาจาก A ทั้งสองS และ D อยู่ติดกับ A แต่เรากังวลสำหรับโหนดที่ไม่ได้เข้าชมเท่านั้น |
4 |
|
เยี่ยมชม Dและทำเครื่องหมายว่าเยี่ยมชมและวางลงในสแต็ก ที่นี่เรามีB และ C โหนดซึ่งอยู่ติดกับ Dและทั้งคู่ยังไม่ได้เยี่ยมชม อย่างไรก็ตามเราจะเลือกตามลำดับตัวอักษรอีกครั้ง |
5 |
|
พวกเราเลือก Bทำเครื่องหมายว่าเยี่ยมชมแล้ววางลงในสแต็ก ที่นี่Bไม่มีโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชม ดังนั้นเราจึงปรากฏB จากกอง |
6 |
|
เราตรวจสอบสแต็กท็อปเพื่อกลับไปยังโหนดก่อนหน้าและตรวจสอบว่ามีโหนดที่ไม่ได้เยี่ยมชมหรือไม่ ที่นี่เราพบD ที่จะอยู่ด้านบนสุดของสแต็ก |
7 |
|
โหนดที่อยู่ติดกันที่ไม่ได้เข้าชมเท่านั้นที่มาจาก D คือ Cตอนนี้. เราจึงไปเยี่ยมชมCทำเครื่องหมายว่าเยี่ยมชมแล้ววางลงในสแต็ก |
เช่น Cไม่มีโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชมดังนั้นเราจึงเปิดสแต็กต่อไปจนกว่าเราจะพบโหนดที่มีโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชม ในกรณีนี้ไม่มีเลยและเราจะโผล่ไปเรื่อย ๆ จนกว่าสแต็กจะว่างเปล่า
หากต้องการทราบข้อมูลเกี่ยวกับการดำเนินการตามขั้นตอนวิธีนี้ในการเขียนโปรแกรมภาษา C ที่คลิกที่นี่