การค้นหาในแนวกว้างก่อน

Breadth-first search[]

ในทฤษฎีของกราฟนั้น Breadth-First Search (BFS) เป็นขั้นตอนการหากราฟทั้งหมด ที่โหนดเริ่มต้น (Root) และทำการสำรวจโหนดของเพื่อนบ้าน การค้นหาแบบกว้างก่อนเป็นการกําหนดทิศทางการค้นหาแบบที่ละระดับของโครงสร้างต้นไม้โดยเริ่มจากโหนดราก(ระดับที่ 0) แล้วลงมาระดับที่ 1 จากซ้ายไปขวา เมื่อเสร็จระดับที่ 1 ไประดับที่ 2จากซ้ายไปขวาเช่นกัน ทําเช่นนี้เรื่อย ๆ จนพบโหนดที่ต้องการตามรูปข้างล่าง ลําดับการเดินทางของโหนดเป็นไปตามหมายเลขที่กํากับไว้บนโหนด

-ความซับซ้อนของพื้นที่ว่าง ทุกโหนดที่ทุกเลเวลต้องมีการเซฟก่อนที่จะโหนดลูกต่อๆไปจะเกิดขึ้นโดยค่า Space Complexity หรือ ความซับซ้อนของพื้นที่ว่าง เป็นเลขของโหนดที่อยู่ลึกสุด โดยแสดงเป็นสูตรคือ O( | V | + | E | ) = O(bd) หรือมีอีกชื่อคือ worst case

-ความซับซ้อนของเวลา เมื่อ Space Complexity ทำการพิจารณาทางทุกเส้นที่สามารถไปได้แล้ว ค่า ความซับซ้อนของเวลาคือ b+b^2+b^3+... ที่เข้าใกล้ O(bd)

ความสมบูรณ์ของกราฟ ( Completeness )

หมายถึงกราฟหลังจากค้นหาแบบ BFS นั้นเป็นจริงทุกๆโมเดล และสามารถพิสูจน์ได้

ความเหมาะสมของกราฟ ( Optimality)

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