แนะนำ, 2024

ตัวเลือกของบรรณาธิการ

ความแตกต่างระหว่าง BFS และ DFS

ข้อแตกต่างที่สำคัญระหว่าง BFS และ DFS คือ BFS ดำเนินการตามระดับในขณะที่ DFS ตามหลังรูปแบบพา ธ เริ่มต้นไปที่โหนดสุดท้าย (จุดสุดยอด) จากนั้นพา ธ อื่นตั้งแต่ต้นจนจบจนถึงโหนดอื่น ๆ นอกจากนี้ BFS ยังใช้คิวในการจัดเก็บโหนดในขณะที่ DFS ใช้สแต็กสำหรับการสำรวจเส้นทางของโหนด

BFS และ DFS เป็นวิธีการสำรวจเส้นทางที่ใช้ในการค้นหากราฟ กราฟการสำรวจเส้นทางเป็นกระบวนการของการเยี่ยมชมทุกโหนดของกราฟ กราฟคือกลุ่มของจุดยอด 'V' และขอบ 'E' ที่เชื่อมต่อกับจุดยอด

แผนภูมิเปรียบเทียบ

พื้นฐานสำหรับการเปรียบเทียบ
BFSDFS
ขั้นพื้นฐานอัลกอริทึมที่ใช้จุดสุดยอดอัลกอริทึมที่ใช้ขอบ
โครงสร้างข้อมูลที่ใช้ในการจัดเก็บโหนดคิวกอง
การใช้หน่วยความจำไม่มีประสิทธิภาพที่มีประสิทธิภาพ
โครงสร้างของต้นไม้ที่สร้างขึ้นกว้างและสั้นแคบและยาว
ภายในแฟชั่นจุดยอดที่เก่าที่สุดที่ไม่เคยมีการสำรวจในตอนแรกมีการสำรวจจุดยอดตามขอบในจุดเริ่มต้น
optimalityเหมาะสมที่สุดสำหรับการค้นหาระยะทางที่สั้นที่สุดไม่ใช่ค่าใช้จ่ายไม่เหมาะสม
ใบสมัครตรวจสอบกราฟสองส่วนส่วนประกอบที่เชื่อมต่อและเส้นทางที่สั้นที่สุดที่อยู่ในกราฟตรวจสอบกราฟที่เชื่อมต่อแบบสองขอบ, กราฟที่เชื่อมต่ออย่างมาก, กราฟอะคริลิคและลำดับโทโพโลยี

คำจำกัดความของ BFS

Breadth First Search (BFS) เป็นวิธีการสำรวจเส้นทางที่ใช้ในกราฟ มันใช้คิวสำหรับการจัดเก็บจุดยอดเยี่ยม ในวิธีการนี้การเน้นอยู่ที่จุดยอดของกราฟจุดยอดหนึ่งจุดจะถูกเลือกในตอนแรกจากนั้นจะมีการเยี่ยมชมและทำเครื่องหมาย จุดยอดที่อยู่ติดกับจุดสุดยอดที่เยี่ยมชมนั้นจะถูกเยี่ยมชมและเก็บไว้ในคิวตามลำดับ ในทำนองเดียวกันจุดยอดที่เก็บไว้จะได้รับการปฏิบัติทีละจุดและเยี่ยมชมจุดยอดที่อยู่ติดกัน โหนดจะถูกสำรวจอย่างสมบูรณ์ก่อนที่จะไปที่โหนดอื่นในกราฟหรือกล่าวอีกนัยหนึ่งมันจะสำรวจโหนดที่ไม่ได้สำรวจตื้นที่สุดก่อน

ตัวอย่าง

เรามีกราฟที่จุดยอดคือ A, B, C, D, E, F, G. พิจารณาว่าเป็นจุดเริ่มต้น ขั้นตอนที่เกี่ยวข้องในกระบวนการคือ:

  • Vertex A ถูกขยายและเก็บไว้ในคิว
  • จุดยอด B, D และ G ของ A จะถูกขยายและเก็บไว้ในคิวขณะที่ Vertex A จะถูกลบออก
  • ตอนนี้ B ที่ส่วนหน้าของคิวจะถูกลบออกพร้อมกับการจัดเก็บตำแหน่งตัวตายตัวแทน E และ F
  • Vertex D อยู่ที่ส่วนหน้าของคิวจะถูกลบออกและโหนดที่เชื่อมต่อของ F ถูกเยี่ยมชมแล้ว
  • Vertex G ถูกลบออกจากคิวและมีตัวตายตัวแทน E ที่ถูกเยี่ยมชมแล้ว
  • ตอนนี้ E และ F จะถูกลบออกจากคิวและจุดสุดยอดตัวตายตัวแทน C จะถูกข้ามและเก็บไว้ในคิว
  • ในที่สุด C จะถูกลบออกและคิวว่างซึ่งหมายความว่าเราทำเสร็จแล้ว
  • ผลลัพธ์ที่ได้คือ - A, B, D, G, E, F, C

โปรแกรมประยุกต์

BFS มีประโยชน์ในการค้นหาว่ากราฟมีการ เชื่อมต่อส่วนประกอบ หรือไม่ และยังสามารถใช้ในการตรวจสอบ กราฟสองฝ่าย

กราฟคือ bipartite เมื่อกราฟจุดยอดถูกแยกออกเป็นสองชุดแยกกัน ไม่มีจุดยอดสองจุดติดกันจะอยู่ในชุดเดียวกัน อีกวิธีหนึ่งในการตรวจสอบกราฟสองส่วนคือการตรวจสอบการเกิดขึ้นของวัฏจักรคี่ในกราฟ กราฟสองส่วนจะต้องไม่มีรอบคี่

BFS นั้นยังดีกว่าในการค้นหา เส้นทางที่สั้นที่สุด ในกราฟที่สามารถมองเห็นเป็นเครือข่าย

คำจำกัดความของ DFS

วิธีการสำรวจ ความลึกการค้นหาครั้งแรก (DFS) ใช้สแต็กสำหรับการจัดเก็บจุดยอดเยี่ยม DFS เป็นวิธีการที่อิงกับขอบและทำงานในแบบเรียกซ้ำที่มีการสำรวจจุดยอดตามเส้นทาง (ขอบ) การสำรวจของโหนดจะถูกระงับทันทีที่พบโหนดที่ไม่ได้สำรวจอีกโหนดและโหนดที่ไม่ได้สำรวจที่ลึกที่สุดจะถูกสำรวจที่สำคัญที่สุด การสำรวจ DFS / การเยี่ยมแต่ละจุดสุดยอดหนึ่งครั้งและแต่ละขอบจะถูกตรวจสอบสองครั้ง

ตัวอย่าง

คล้ายกับ BFS ให้ใช้กราฟเดียวกันสำหรับการดำเนินการ DFS และขั้นตอนที่เกี่ยวข้องคือ:

  • พิจารณา A เป็นจุดเริ่มต้นซึ่งสำรวจและเก็บไว้ในสแต็ก
  • จุดต่อเนื่องของ B จะถูกเก็บไว้ในสแต็ก
  • Vertex B มีผู้สืบทอดสองคนคือ E และ F ซึ่งเป็นผู้ที่มีลำดับตัวอักษร E จะถูกสำรวจก่อนและเก็บไว้ในสแต็ก
  • ตัวต่อของจุดยอด E คือ G ถูกเก็บไว้ในสแต็ก
  • Vertex G มีจุดเชื่อมต่อสองจุดและทั้งคู่ถูกเยี่ยมชมแล้วดังนั้น G จึงถูกดึงออกมาจากสแต็ก
  • ในทำนองเดียวกัน E s ก็ถูกลบไปด้วย
  • ตอนนี้จุดยอด B อยู่ที่ด้านบนสุดของสแต็กอีกโหนดหนึ่ง (จุดยอด) F จะถูกสำรวจและเก็บไว้ในสแต็ก
  • Vertex F มีตัวตายตัวแทน C และ D สองตัวระหว่างพวกมัน C จะถูกสำรวจก่อนและเก็บไว้ในสแต็ก
  • Vertex C มีเพียงหนึ่งรุ่นก่อนที่มีการเยี่ยมชมอยู่แล้วดังนั้นจึงถูกลบออกจากสแต็ก
  • ตอนนี้จุดยอด D ที่เชื่อมต่อกับ F จะถูกเยี่ยมชมและเก็บไว้ในสแต็ก
  • เนื่องจากจุดยอด D ไม่มีโหนดที่ไม่ได้เข้าชมดังนั้น D จะถูกลบ
  • ในทำนองเดียวกัน F, B และ A ก็โผล่ขึ้นมา
  • ผลลัพธ์ที่สร้างขึ้นคือ - A, B, E, G, F, C, D

โปรแกรมประยุกต์

แอพพลิเคชั่นของ DFS นั้นรวมถึงการตรวจสอบกราฟที่ เชื่อมต่อกับขอบทั้งสอง, กราฟที่ เชื่อมต่ออย่างยิ่ง, กราฟอะค ริลิคและ ลำดับทอพอโลยี

กราฟจะถูกเรียกว่าสองขอบเชื่อมต่อถ้าหากยังคงมีการเชื่อมต่ออยู่แม้ว่าจะมีการลบขอบด้านใดด้านหนึ่ง แอปพลิเคชั่นนี้มีประโยชน์มากในเครือข่ายคอมพิวเตอร์ที่ความล้มเหลวของลิงค์เดียวในเครือข่ายจะไม่ส่งผลกระทบต่อเครือข่ายที่เหลือและจะยังคงเชื่อมต่ออยู่

กราฟที่เชื่อมต่ออย่างมากคือกราฟที่ต้องมีเส้นทางระหว่างจุดยอดสั่งซื้อคู่ DFS ใช้ในกราฟกำกับเพื่อค้นหาเส้นทางระหว่างจุดยอดสั่งซื้อทุกคู่ DFS สามารถแก้ปัญหาการเชื่อมต่อได้อย่างง่ายดาย

ความแตกต่างที่สำคัญระหว่าง BFS และ DFS

  1. BFS เป็นอัลกอริทึมที่ใช้จุดสุดยอดในขณะที่ DFS เป็นอัลกอริทึมที่ใช้ขอบ
  2. โครงสร้างข้อมูลคิวถูกใช้ใน BFS ในทางกลับกัน DFS ใช้กองซ้อนหรือเรียกซ้ำ
  3. พื้นที่หน่วยความจำถูกใช้อย่างมีประสิทธิภาพใน DFS ในขณะที่การใช้พื้นที่ใน BFS ไม่มีประสิทธิภาพ
  4. BFS เป็นอัลกอริธึมที่เหมาะสมที่สุดในขณะที่ DFS ไม่เหมาะสมที่สุด
  5. DFS สร้างต้นไม้ที่แคบและยาว เมื่อเทียบกับ BFS สร้างต้นไม้กว้างและสั้น

ข้อสรุป

BFS และ DFS ทั้งสองเทคนิคการค้นหากราฟมีเวลาทำงานคล้ายกัน แต่สิ้นเปลืองพื้นที่แตกต่างกัน DFS ใช้พื้นที่เชิงเส้นเนื่องจากเราต้องจำเส้นทางเดียวด้วยโหนดที่ไม่ได้สำรวจในขณะที่ BFS เก็บทุกโหนดในหน่วยความจำ

DFS ให้โซลูชันที่ลึกกว่าและไม่เหมาะสม แต่จะทำงานได้ดีเมื่อโซลูชันมีความหนาแน่นสูงในขณะที่ BFS นั้นเหมาะสมที่สุดซึ่งจะค้นหาเป้าหมายที่เหมาะสมที่สุดในตอนแรก

Top