BFS กับ DFS - ความแตกต่างระหว่างพวกเขา

บีเอฟเอสคืออะไร?

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

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

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

DFS คืออะไร?

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

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

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

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

ตัวอย่างของบีเอฟเอส

ในตัวอย่างของ BFS ต่อไปนี้ เราใช้กราฟที่มีจุดยอด 6 จุด

ตัวอย่างของบีเอฟเอส

ขั้นตอน 1)

คุณมีกราฟของตัวเลขเจ็ดตัวตั้งแต่ 0 – 6

ขั้นตอน 2)

0 หรือศูนย์ถูกทำเครื่องหมายเป็นโหนดรูท

ขั้นตอน 3)

0 ถูกเยี่ยมชม ทำเครื่องหมาย และแทรกลงในโครงสร้างข้อมูลคิว

ขั้นตอน 4)

โหนดที่อยู่ติดกันและที่ไม่ได้เยี่ยมชมที่เหลืออยู่ 0 รายการจะถูกเยี่ยมชม ทำเครื่องหมาย และแทรกลงในคิว

ขั้นตอน 5)

การวนซ้ำตามเส้นทางจะถูกทำซ้ำจนกว่าจะมีการเยี่ยมชมโหนดทั้งหมด

ตัวอย่างของ DFS

ในตัวอย่าง DFS ต่อไปนี้ เราใช้กราฟไม่มีทิศทางซึ่งมีจุดยอด 5 จุด

ขั้นตอน 1)

เราเริ่มต้นจากจุดยอด 0 อัลกอริทึมเริ่มต้นด้วยการใส่จุดยอดนั้นลงในรายการที่เยี่ยมชมและวางจุดยอดที่อยู่ติดกันทั้งหมดพร้อมกันใน โครงสร้างข้อมูล เรียกว่าสแต็ค

ขั้นตอน 2)

คุณจะไปที่องค์ประกอบซึ่งอยู่ที่ด้านบนของสแต็ก เช่น 1 และไปที่โหนดที่อยู่ติดกัน เป็นเพราะ 0 ได้ถูกเยี่ยมชมแล้ว ดังนั้นเราจึงไปที่จุดยอด 2

ขั้นตอน 3)

จุดยอด 2 มีจุดยอดใกล้เคียงที่ไม่มีใครเยี่ยมชมใน 4 ดังนั้นเราจึงเพิ่มจุดนั้นลงในสแต็กและเยี่ยมชมจุดนั้น

ขั้นตอน 4)

สุดท้าย เราจะไปที่จุดยอด 3 สุดท้าย ซึ่งไม่มีโหนดที่อยู่ติดกันที่ยังไม่ได้เยี่ยมชม เราได้เสร็จสิ้นการสำรวจกราฟโดยใช้อัลกอริทึม DFS

แอพพลิเคชั่นของบีเอฟเอส

นี่คือแอปพลิเคชันของ BFS:

กราฟที่ไม่ถ่วงน้ำหนัก

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

เครือข่าย P2P

BFS สามารถนำมาใช้เพื่อค้นหาโหนดที่อยู่ใกล้หรืออยู่ติดกันทั้งหมดในเครือข่ายเพียร์ทูเพียร์ ซึ่งจะทำให้ค้นหาข้อมูลที่ต้องการได้เร็วขึ้น

โปรแกรมรวบรวมข้อมูลเว็บ

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

การแพร่ภาพกระจายเสียงผ่านเครือข่าย

แพ็กเก็ตที่ออกอากาศจะถูกแนะนำโดยอัลกอริธึม BFS เพื่อค้นหาและเข้าถึงโหนดทั้งหมดที่มีที่อยู่นั้น

การประยุกต์ใช้ DFS

นี่คือการใช้งานที่สำคัญของ DFS:

กราฟถ่วงน้ำหนัก

ในกราฟถ่วงน้ำหนัก การข้ามกราฟ DFS จะสร้างแผนผังเส้นทางที่สั้นที่สุดและแผนผังการขยายขั้นต่ำ

การตรวจจับวงจรในกราฟ

กราฟจะมีวงจรหากเราพบขอบด้านหลังระหว่าง DFS ดังนั้นเราจึงควรรัน DFS สำหรับกราฟและตรวจสอบขอบด้านหลัง

ค้นหาเส้นทาง

เราสามารถเชี่ยวชาญในอัลกอริธึม DFS เพื่อค้นหาเส้นทางระหว่างจุดยอดสองจุด

การเรียงลำดับโทโพโลยี

ส่วนใหญ่จะใช้เพื่อจัดกำหนดการงานจากความสัมพันธ์ที่กำหนดระหว่างกลุ่มงาน ในวิทยาการคอมพิวเตอร์ ใช้ในการจัดกำหนดการคำสั่ง การจัดลำดับข้อมูล การสังเคราะห์ตรรกะ และการกำหนดลำดับของงานคอมไพล์

การค้นหาส่วนประกอบของกราฟที่เชื่อมต่อกันอย่างแน่นแฟ้น

ใช้ในกราฟ DFS เมื่อมีเส้นทางจากแต่ละจุดยอดในกราฟไปยังจุดยอดอื่นๆ ที่เหลือ

การไขปริศนาด้วยวิธีแก้ปัญหาเพียงวิธีเดียว

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