BFS และ DFS เป็นวิธีการสำรวจเส้นทางที่ใช้ในการค้นหากราฟ กราฟการสำรวจเส้นทางเป็นกระบวนการของการเยี่ยมชมทุกโหนดของกราฟ กราฟคือกลุ่มของจุดยอด 'V' และขอบ 'E' ที่เชื่อมต่อกับจุดยอด
แผนภูมิเปรียบเทียบ
| พื้นฐานสำหรับการเปรียบเทียบ | BFS | DFS |
|---|---|---|
| ขั้นพื้นฐาน | อัลกอริทึมที่ใช้จุดสุดยอด | อัลกอริทึมที่ใช้ขอบ |
| โครงสร้างข้อมูลที่ใช้ในการจัดเก็บโหนด | คิว | กอง |
| การใช้หน่วยความจำ | ไม่มีประสิทธิภาพ | ที่มีประสิทธิภาพ |
| โครงสร้างของต้นไม้ที่สร้างขึ้น | กว้างและสั้น | แคบและยาว |
| ภายในแฟชั่น | จุดยอดที่เก่าที่สุดที่ไม่เคยมีการสำรวจในตอนแรก | มีการสำรวจจุดยอดตามขอบในจุดเริ่มต้น |
| 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
- BFS เป็นอัลกอริทึมที่ใช้จุดสุดยอดในขณะที่ DFS เป็นอัลกอริทึมที่ใช้ขอบ
- โครงสร้างข้อมูลคิวถูกใช้ใน BFS ในทางกลับกัน DFS ใช้กองซ้อนหรือเรียกซ้ำ
- พื้นที่หน่วยความจำถูกใช้อย่างมีประสิทธิภาพใน DFS ในขณะที่การใช้พื้นที่ใน BFS ไม่มีประสิทธิภาพ
- BFS เป็นอัลกอริธึมที่เหมาะสมที่สุดในขณะที่ DFS ไม่เหมาะสมที่สุด
- DFS สร้างต้นไม้ที่แคบและยาว เมื่อเทียบกับ BFS สร้างต้นไม้กว้างและสั้น
ข้อสรุป
BFS และ DFS ทั้งสองเทคนิคการค้นหากราฟมีเวลาทำงานคล้ายกัน แต่สิ้นเปลืองพื้นที่แตกต่างกัน DFS ใช้พื้นที่เชิงเส้นเนื่องจากเราต้องจำเส้นทางเดียวด้วยโหนดที่ไม่ได้สำรวจในขณะที่ BFS เก็บทุกโหนดในหน่วยความจำ
DFS ให้โซลูชันที่ลึกกว่าและไม่เหมาะสม แต่จะทำงานได้ดีเมื่อโซลูชันมีความหนาแน่นสูงในขณะที่ BFS นั้นเหมาะสมที่สุดซึ่งจะค้นหาเป้าหมายที่เหมาะสมที่สุดในตอนแรก
