DFS เยี่ยมชมจุดยอดย่อยก่อนที่จะเยี่ยมชมจุดยอดพี่น้อง กล่าวคือ มันสำรวจความลึกของเส้นทางใด ๆ ก่อนสำรวจความกว้างของมัน โดยทั่วไปแล้ว stack (มักจะเป็น call stack ของโปรแกรมผ่านการเรียกซ้ำ) ถูกใช้เมื่อนำอัลกอริทึมไปใช้
ต่อไปนี้เป็นวิธีการทำงานของ DFS -
- เยี่ยมชมจุดยอดที่ไม่ได้เยี่ยมชมที่อยู่ติดกัน ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงมัน ดันเป็นกอง
- หากไม่พบจุดยอดที่อยู่ติดกัน ให้เปิดจุดยอดจากสแต็ก (มันจะแสดงจุดยอดทั้งหมดจากสแต็ก ซึ่งไม่มีจุดยอดที่อยู่ติดกัน)
- ทำซ้ำกฎ 1 และกฎ 2 จนกว่าสแต็กจะว่างเปล่า
ให้เรามาดูภาพประกอบว่า DFS Traversal ทำงานอย่างไร
| ขั้นตอน | การเดินทาง | คำอธิบาย |
|---|---|---|
| 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 ไม่มีโหนดที่อยู่ติดกันที่ยังไม่ได้เยี่ยมชม ดังนั้นเราจึงเปิดสแต็กต่อไปจนกว่าเราจะพบโหนดที่มีโหนดที่อยู่ติดกันที่ยังไม่ได้เยี่ยมชม ในกรณีนี้ จะไม่มีและเราจะแสดงต่อไปจนกว่าสแต็กจะว่างเปล่า มาดูกันว่าเราจะใช้สิ่งนี้ใน JavaScript ได้อย่างไร
ตัวอย่าง
DFS(node) {
// Create a Stack and add our initial node in it
let s = new Stack(this.nodes.length);
let explored = new Set();
s.push(node);
// Mark the first node as explored
explored.add(node);
// We'll continue till our Stack gets empty
while (!s.isEmpty()) {
let t = s.pop();
// Log every element that comes out of the Stack
console.log(t);
// 1. In the edges object, we search for nodes this node is directly connected to.
// 2. We filter out the nodes that have already been explored.
// 3. Then we mark each unexplored node as explored and push it to the Stack.
this.edges[t]
.filter(n => !explored.has(n))
.forEach(n => {
explored.add(n);
s.push(n);
});
}
} นั่นเป็นเรื่องง่าย เราเพิ่งเปลี่ยนคิวสำหรับสแต็กและ voila เรามี DFS นั่นเป็นข้อแตกต่างเพียงอย่างเดียวระหว่าง 2 DFS ที่สามารถใช้งานได้โดยใช้การเรียกซ้ำ แต่ควรหลีกเลี่ยงในกรณีนี้ เนื่องจากกราฟที่ใหญ่ขึ้นหมายความว่าเราต้องการหน่วยความจำเพิ่มเติมเพียงเพื่อติดตาม call stack
คุณสามารถทดสอบได้โดยใช้ −
let g = new Graph();
g.addNode("A");
g.addNode("B");
g.addNode("C");
g.addNode("D");
g.addNode("E");
g.addNode("F");
g.addNode("G");
g.addEdge("A", "C");
g.addEdge("A", "B");
g.addEdge("A", "D");
g.addEdge("D", "E");
g.addEdge("E", "F");
g.addEdge("B", "G");
g.DFS("A"); ผลลัพธ์
สิ่งนี้จะให้ผลลัพธ์
A D E F B G C
