การค้นหาข้อมูลแบบ Breadth First Search (BFS) ด้วยภาษา Kotlin

 

 

คำแนะนำเบื้องต้นเกี่ยวกับ BFS

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

การใช้งาน BFS

BFS มักจะถูกใช้ในหลายสถานการณ์ที่ต้องการค้นหาหรือประเมินระยะทางระหว่างจุดต่างๆ หรือในการค้นหาเส้นทางที่สั้นที่สุดในกราฟ เช่น:

- การค้นหาเพื่อนใหม่ในโซเชียลมีเดีย

- การค้นหาสถานที่ต่างๆ ในแผนที่

- การหาเส้นทางที่สั้นที่สุดในโลจิสติกส์

 

ตัวอย่างโค้ด BFS ในภาษา Kotlin

ด้านล่างนี้คือโค้ดตัวอย่างการค้นหาแบบ BFS ในภาษา Kotlin:

 import java.util.*

class Graph(val vertices: Int) {
    private val adjList: Array<MutableList<Int>> = Array(vertices) { mutableListOf() }

    fun addEdge(v: Int, w: Int) {
        adjList[v].add(w)
    }

    fun bfs(start: Int) {
        val visited = BooleanArray(vertices)
        val queue: Queue<Int> = LinkedList()

        visited[start] = true
        queue.offer(start)

        while (queue.isNotEmpty()) {
            val vertex = queue.poll()
            println("Visited vertex: $vertex")

            for (neighbor in adjList[vertex]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true
                    queue.offer(neighbor)
                }
            }
        }
    }
}

ในโค้ดด้านบน เราได้สร้างคลาส `Graph` ที่มีฟังก์ชัน `addEdge` เพื่อเพิ่มขอบในกราฟ จากนั้นเราก็ได้สร้างฟังก์ชัน `bfs` เพื่อเริ่มการค้นหาแบบ BFS เริ่มจากโหนดเริ่มต้นที่เราให้ไป

การใช้งานโค้ด

ลองมาใช้โค้ดนี้เพื่อสร้างกราฟง่ายๆ และทำการค้นหากันดู:

 fun main() {
    val graph = Graph(6)
    graph.addEdge(0, 1)
    graph.addEdge(0, 2)
    graph.addEdge(1, 3)
    graph.addEdge(1, 4)
    graph.addEdge(2, 5)

    println("Breadth First Search starting from vertex 0:")
    graph.bfs(0)
}

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

 

วิเคราะห์ Complexity

อัลกอริธึม BFS มีความซับซ้อนเวลา (Time Complexity) เป็น O(V + E) ซึ่ง V คือจำนวนโหนด (vertices) ในกราฟ และ E คือจำนวนขอบ (edges) ส่วนความซับซ้อนพื้นที่ (Space Complexity) ก็เป็น O(V) สำหรับโครงสร้างข้อมูลที่ใช้จัดเก็บการเยี่ยมชมให้ตรวจสอบว่าโหนดไหนได้ถูกเยี่ยมชมไปแล้ว

ข้อดีของ BFS

- ค้นหาเส้นทางที่สั้นที่สุด: ในกราฟที่ไม่มีน้ำหนัก ข้อดีที่ชัดเจนคือ BFS สามารถให้เส้นทางที่สั้นที่สุดจากจุดเริ่มต้นไปยังจุดหมายได้ - สำรวจระดับข้อมูล: BFS สามารถใช้ได้ดีในกราฟที่มีข้อมูลเชิงเนื้อที่ต้นไม้ (Tree Structure) ช่วยให้เราสามารถสำรวจข้อมูลในหลายระดับได้

ข้อเสียของ BFS

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

 

สรุป

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

หากคุณสนใจเรียนรู้เพิ่มเติมเกี่ยวกับการเขียนโปรแกรมและกราฟอัลกอริธึมอื่นๆ อย่าลืมเข้าร่วมการเรียนรู้กับ EPT (Expert-Programming-Tutor) เรามีหลักสูตรที่รองรับทุกระดับเพื่อพัฒนาทักษะของคุณในโลกของการเขียนโปรแกรม!

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

 

 

หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง