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 เช่นกัน
Example[]
ตัวอย่างที่ 1 ที่ภาพจะเห็นการเดินทางไปแต่ละโหนดของ BFS ได้อย่างชัดเจน
ตัวอย่างที่ 2
คำที่เกี่ยวข้อง[]
Depth-first search
graph search algorithm
bipartiteness
เอกสารอ้างอิง[]
Knuth, Donald E. (1997), The Art Of Computer Programming Vol 1. 3rd ed., Boston: Addison-Wesley, ISBN 0-201-89683-4
http://202.28.94.55/web/320417/2548/work1/g25/technoreport1.htm