การค้นหาแบบกว้าง (Breadth First Search) ด้วยภาษา Swift

 

 

แนะนำ Algorithm Breadth First Search (BFS)

Breadth First Search (BFS)

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

 

การใช้งาน BFS

BFS มักถูกนำไปใช้ในการแก้ปัญหาหลาย ๆ ด้าน เช่น:

- การค้นหาเส้นทางที่สั้นที่สุด ในกราฟ เช่น เส้นทางในแผนที่ - การค้นหาในระบบฐานข้อมูลง เช่น การค้นหาข้อมูลในฐานข้อมูล - การวิเคราะห์เครือข่ายสังคม เช่น การหาเพื่อนที่เชื่อมโยงกัน

 

ตัวอย่าง Code

ในตัวอย่างนี้เราจะทำการใช้ BFS เพื่อค้นหาทุกๆ โหนดในกราฟอย่างง่ายด้วยภาษา Swift

 import Foundation

class Graph {
    var adjList: [Int: [Int]] = [:]

    func addEdge(from source: Int, to destination: Int) {
        if adjList[source] == nil {
            adjList[source] = []
        }
        adjList[source]?.append(destination)
    }

    func bfs(start: Int) {
        var visited = Set<Int>()
        var queue = [start]

        visited.insert(start)

        while !queue.isEmpty {
            let node = queue.removeFirst()
            print("Visited: \(node)")

            if let neighbors = adjList[node] {
                for neighbor in neighbors {
                    if !visited.contains(neighbor) {
                        visited.insert(neighbor)
                        queue.append(neighbor)
                    }
                }
            }
        }
    }
}

// Usage
let graph = Graph()
graph.addEdge(from: 1, to: 2)
graph.addEdge(from: 1, to: 3)
graph.addEdge(from: 2, to: 4)
graph.addEdge(from: 2, to: 5)
graph.addEdge(from: 3, to: 6)

print("BFS starting from node 1:")
graph.bfs(start: 1)

ในตัวอย่างข้างต้น เราได้สร้างคลาส `Graph` ขึ้นมาเพื่อจัดการกับกราฟ และมีฟังก์ชัน `bfs` ที่ใช้ในการค้นหาโหนด โดยมีการใช้ `visited` ที่เป็น `Set` เพื่อจดบันทึกโหนดที่เราได้เข้าไปเยี่ยมชมแล้ว เพื่อป้องกันไม่ให้เราเข้าไปเยี่ยมชมโหนดเดิมซ้ำอีก

 

Complexity Analysis

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

 

ข้อดีข้อเสียของ BFS

ข้อดี:

1. ค้นหาเส้นทางที่สั้นที่สุด: ในกราฟที่มีการเชื่อมโยงระหว่างโหนดอย่างเท่ากัน BFS จะสามาถค้นหาเส้นทางที่สั้นที่สุดได้ 2. เข้าถึงระดับใกล้ที่สุดก่อน: กระบวนการทำงานของ BFS มักจะช่วยให้พบข้อมูลที่อยู่ใกล้เคียงก่อน ซึ่งมีประโยชน์ในหลายกรณี

ข้อเสีย:

1. ใช้พื้นที่มาก: เนื่องจากต้องเก็บโหนดในคิวอาจทำให้การใช้หน่วยความจำเพิ่มขึ้น 2. ไม่สามารถใช้ได้สำหรับกราฟที่มีน้ำหนัก: BFS ไม่สามารถหาเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักได้ เช่น ในกรณีที่มีค่าใช้จ่ายในการเดินทางแตกต่างกัน

 

Use Cases ในโลกจริง

1. การค้าน: BFS สามารถใช้ในการค้นหาทางที่อย่างรวดเร็วระหว่างจุด A และ B ทำให้ธุรกิจสามารถลดระยะเวลาในการจัดส่งสินค้าได้ 2. การเข้าถึงข้อมูลในฐานข้อมูล: หากจำเป็นต้องค้นหาข้อมูลในฐานข้อมูลที่มีความซับซ้อนและเชื่อมโยงกัน การใช้ BFS จะทำให้สามารถค้นหาได้อย่างรวดเร็วและมีประสิทธิภาพ

 

สรุป

Algorithm Breadth First Search (BFS) เป็นเครื่องมือที่มีประสิทธิภาพสำหรับการค้นหาข้อมูลในกราฟและต้นไม้ แต่ควรพิจารณาข้อจำกัดและข้อดีในการใช้งานด้วยเสมอ หากคุณอยากรู้เพิ่มเติมเกี่ยวกับ Algorithm ต่าง ๆ และการเขียนโปรแกรม อย่าลืมมาศึกษาที่ EPT (Expert-Programming-Tutor) ซึ่งเป็นโรงเรียนสอนการเขียนโปรแกรมโดยผู้เชี่ยวชาญที่พร้อมจะนำคุณสู่โลกของการเขียนโปรแกรมอย่างเต็มที่!

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

 

 

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