home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Javascript

การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript

DFS เยี่ยมชมจุดยอดย่อยก่อนที่จะเยี่ยมชมจุดยอดพี่น้อง กล่าวคือ มันสำรวจความลึกของเส้นทางใด ๆ ก่อนสำรวจความกว้างของมัน โดยทั่วไปแล้ว stack (มักจะเป็น call stack ของโปรแกรมผ่านการเรียกซ้ำ) ถูกใช้เมื่อนำอัลกอริทึมไปใช้

ต่อไปนี้เป็นวิธีการทำงานของ DFS -

  • เยี่ยมชมจุดยอดที่ไม่ได้เยี่ยมชมที่อยู่ติดกัน ทำเครื่องหมายว่าเยี่ยมชมแล้ว แสดงมัน ดันเป็นกอง
  • หากไม่พบจุดยอดที่อยู่ติดกัน ให้เปิดจุดยอดจากสแต็ก (มันจะแสดงจุดยอดทั้งหมดจากสแต็ก ซึ่งไม่มีจุดยอดที่อยู่ติดกัน)
  • ทำซ้ำกฎ 1 และกฎ 2 จนกว่าสแต็กจะว่างเปล่า

ให้เรามาดูภาพประกอบว่า DFS Traversal ทำงานอย่างไร

ขั้นตอน การเดินทาง คำอธิบาย
1 การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript เริ่มต้นสแต็ก
2 การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript มาร์ค S ตามที่เยี่ยมชมและวางไว้บนกอง สำรวจโหนดที่อยู่ติดกันที่ยังไม่ได้เยี่ยมชมจาก S . เรามีสามโหนดและเราสามารถเลือกโหนดใดก็ได้ สำหรับตัวอย่างนี้ เราจะใช้โหนดตามลำดับตัวอักษร
3 การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript มาร์ค A ตามที่เยี่ยมชมและวางไว้บนกอง สำรวจโหนดที่อยู่ติดกันที่ยังไม่ได้เยี่ยมชมจาก A . ทั้ง S และ D อยู่ติดกับ A แต่เรากังวลกับโหนดที่ไม่ได้เยี่ยมชมเท่านั้น
4 การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript เยี่ยมชม D และทำเครื่องหมายว่าเยี่ยมชมแล้ววางลงบนกอง ที่นี่ เรามี B และ C โหนดซึ่งอยู่ติดกับ D และทั้งสองก็ไม่มีใครมาเยี่ยมเยียน อย่างไรก็ตาม เราจะเลือกตามลำดับตัวอักษรอีกครั้ง
5 การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript เราเลือก B ทำเครื่องหมายว่าเยี่ยมชมแล้ววางลงบนกอง ที่นี่ B ไม่มีโหนดที่อยู่ติดกันที่ยังไม่ได้เยี่ยมชม เราก็เลย B จากกอง
6 การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript เราตรวจสอบบนสแต็กด้านบนเพื่อกลับไปยังโหนดก่อนหน้าและตรวจสอบว่ามีโหนดที่ยังไม่ได้เยี่ยมชมหรือไม่ ที่นี่เราพบ D ที่จะอยู่บนสุดของกอง
7 การข้ามผ่านการค้นหาเชิงลึกเป็นอันดับแรกใน Javascript เฉพาะโหนดที่อยู่ติดกันที่ไม่ได้เยี่ยมชมเท่านั้นที่มาจาก 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