Loading AI tools
จากวิกิพีเดีย สารานุกรมเสรี
ในทฤษฎีกราฟ การค้นหาตามแนวกว้าง (อังกฤษ: breadth-first search หรือย่อว่า BFS) คือขั้นตอนวิธีในการท่องกราฟอย่างหนึ่ง โดยในขณะที่กำลังท่องกราฟมายังจุดยอดหนึ่ง ๆ นั้น จะมีการกระทำสองอย่างคือ: (ก) เข้าเยี่ยมและตรวจสอบจุดยอดดังกล่าว (ข) เข้าถึงจุดยอดข้างเคียงของจุดยอดดังกลาว การท่องกราฟจะเริ่มต้นที่จุดยอดรากที่กำหนดและไปยังจุดยอดอื่น ๆ จนเกิดเป็นต้นไม้แบบทอดข้าม การท่องกราฟอีกรูปแบบที่คล้ายคลึงกันคือการค้นหาในแนวลึก
การค้นในลักษณะนี้ถูกใช้เป็นแนวคิดพื้นฐานในการแก้ปัญหาทฤษฏีกราฟรวมถึงการค้นในปริภูมิสถานะ
เนื่องจากมีลักษณะของการแวะผ่านปมไปทีละระดับ จึงเรียกอีกอย่างว่า การค้นทีละระดับ (Level-order search)
การค้นตามแนวกว้าง มีลักษณะการค้นหาลงไปทีละระดับ โดยการตรวจสอบระดับลูกทั้งหมดก่อน จึงลงไประดับถัดไป ซึ่งสามารถสร้างการค้นแบบนี้โดยใช้แถวคอย เพื่อให้ปมถูกค้นตามลำดับของระดับชั้น
เนื่องจากการค้นแบบนี้เป็นการค้นที่มีระบบ กล่าวคือไม่มีการตัดสินใจเลือกเส้นทางระหว่างการค้น แต่จะทำการค้นไปเรื่อยๆ ตามรูปแบบจนเจอคำตอบ จึงจัดอยู่ในกลุ่มของการค้นแบบ Blind Search หรือ Uniformed Search
BFS(G(V,E), s) { for each v in V { color[v] <- WHITE; } Q = an empty queue; Q.enqueue(s); color[s] <- GRAY while (Q is not an empty queue) { u <- Q.dequeue(); color[u] <- BLACK; for(each v that adjacent with u) { if(color[v]=WHITE) { Q.enqueue(v); color[v] = GRAY; } } } }
Arad > Timisora > Zerind > Sibiu > Craivora > Oradea > Rimnicu > Fagaras > Pitesti > Bucharest
การค้นตามแนวกว้างสามารถใช้ในการแก้ปัญหาต่างๆของทฤษฏีกราฟได้เช่น
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.