FANDOM


Breadth-first search Edit

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

Image008


-ความซับซ้อนของพื้นที่ว่าง ทุกโหนดที่ทุกเลเวลต้องมีการเซฟก่อนที่จะโหนดลูกต่อๆไปจะเกิดขึ้นโดยค่า 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 Edit

ตัวอย่างที่ 1 ที่ภาพจะเห็นการเดินทางไปแต่ละโหนดของ BFS ได้อย่างชัดเจน

Animated BFS


ตัวอย่างที่ 2


Step 1 Bfs1

Step 2 Bfs2

Step 3 Bfs3

Step 4 Bfs4

Step 5 Bfs5

Step 6 Bfs6

Step 7 Bfs7

Step 8 Bfs8

Step 9 Bfs9

คำที่เกี่ยวข้อง Edit

Depth-first search

graph search algorithm

bipartiteness


เอกสารอ้างอิง Edit

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