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

 

 

วิกฤตของปัญหาในการค้นหา

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

 

BFS คืออะไร?

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

Use Case ของ BFS

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

 

ตัวอย่าง Code โดยใช้ VBA

เพื่อให้เห็นภาพชัดเจนขึ้น เราจะยกตัวอย่างโค้ดที่ใช้ VBA ในการสร้างกราฟและใช้ BFS ในการค้นหาจุดหมายปลายทาง

 Option Explicit

Sub BreadthFirstSearch()
    Dim graph As Object
    Set graph = CreateObject("Scripting.Dictionary")

    ' กำหนดกราฟเป็นแบบ Adjacent List
    graph.Add "A", Array("B", "C")
    graph.Add "B", Array("D", "E")
    graph.Add "C", Array("F")
    graph.Add "D", Array()
    graph.Add "E", Array()
    graph.Add "F", Array()

    Dim startNode As String
    startNode = "A"

    Dim queue As Collection
    Set queue = New Collection
    Dim visited As Object
    Set visited = CreateObject("Scripting.Dictionary")

    queue.Add startNode
    visited.Add startNode, True

    Dim currentNode As String
    Do While queue.Count > 0
        currentNode = queue(1)
        Debug.Print currentNode   ' แสดงผลปัจจุบัน

        Dim neighbors As Variant
        neighbors = graph(currentNode)

        Dim n As Variant
        For Each n In neighbors
            If Not visited.Exists(n) Then
                visited.Add n, True
                queue.Add n
            End If
        Next n

        queue.Remove 1  ' ลบ node ที่ถูกเยี่ยมชมแล้ว
    Loop
End Sub

ในตัวอย่างนี้ เราสร้างกราฟง่ายๆ โดยแต่ละ `key` คือ node และ `value` คือ array ของ neighbors การทำงานของ BFS จะเริ่มจาก node ที่ระบุ (ในที่นี้คือ "A") และในแต่ละขั้นตอนจะบันทึก node ที่เยี่ยมชมแล้วเพื่อหลีกเลี่ยงการซ้ำซ้อน

 

วิเคราะห์ Complexity ของ BFS

Time Complexity

BFS มี Time Complexity อยู่ที่ O(V + E) โดยที่ V คือจำนวน vertices (node) และ E คือจำนวน edges (เส้นเชื่อมระหว่าง node) วิธีการนี้ทำงานโดยตรวจสอบทุก node และทุก edge ในกราฟ

Space Complexity

Space Complexity

ของ BFS จะอยู่ที่ O(V) เนื่องจากเราต้องจัดเก็บ node ที่อนุญาตให้เยี่ยมชมไว้ใน queue รวมถึง dictionary ที่ใช้อยู่ใน visited

 

ข้อดีและข้อเสียของ Algorithm BFS

ข้อดี

- BFS สามารถให้ผลลัพธ์ที่เป็นเส้นทางที่สั้นที่สุดในกราฟที่ไม่มีป้ายกำกับน้ำหนัก

- นำไปใช้เพื่อค้นหาความเชื่อมโยงในโครงสร้างข้อมูลแบบกราฟ

ข้อเสีย

- ต้องใช้หน่วยความจำจำนวนมาก โดยเฉพาะในกราฟที่มีเส้นเชื่อมที่มาก ซึ่งอาจจะต้องใช้ทรัพยากรสูง

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

 

สรุป

BFS เป็น Algorithm ที่สำคัญสำหรับนักพัฒนาโปรแกรมในการค้นหาข้อมูลในโครงสร้างที่ซับซ้อน ไม่ว่าจะเป็นกราฟหรือต้นไม้ การเรียนรู้และเข้าใจ BFS จะช่วยเพิ่มศักยภาพในการจัดการข้อมูลที่หลากหลายมากขึ้น

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

มาเริ่มการเดินทางในโลกของการเขียนโปรแกรมกับ EPT กันเถอะ!

 

 

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