การค้นหาฐานกว้าง (Breadth First Search) ด้วยภาษา Scala

 

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

 

BFS คืออะไร?

Breadth First Search คือ อัลกอริธึมที่ใช้ในการค้นหาและสำรวจกราฟ โดยเริ่มต้นที่จุดต้น (เริ่มที่ Node/Musi) และใช้แนวทางการสำรวจระดับ (Level-wise) หรือชั้นในโครงสร้าง โดยจะสำรวจ Node ใกล้เคียงก่อนแล้วจึงทำการสำรวจ Node ถัดไปในระดับเดียวกันไปเรื่อย ๆ จนกว่าจะพบ Node ที่ต้องการหรือจนกว่าจะสำรวจทุก Node ในกราฟ

การใช้งานของ BFS

BFS มักถูกใช้ในการแก้ปัญหาต่าง ๆ ไม่ว่าจะเป็น

- การหาทางสั้นที่สุดในกราฟที่ไม่ปรากฏน้ำหนัก (Unweighted Graph)

- การสร้างโครงสร้างข้อมูลที่เป็นต้นไม้

- การค้นหาเส้นทางในระบบเครือข่าย

- การวิเคราะห์ข้อมูลในฐานข้อมูล (Database)

 

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

เรามาเริ่มเขียนโค้ดกันดีกว่า โดยจะแสดงตัวอย่าง BFS ในการสำรวจกราฟที่กำหนดไว้ในรูปแบบของลิสต์เชื่อมโยง (Adjacency List) ครับ

 import scala.collection.mutable

object BFSExample {

  def bfs(graph: Map[Int, List[Int]], start: Int): List[Int] = {
    val visited = mutable.Set[Int]()
    val queue = mutable.Queue[Int]()
    val result = mutable.ListBuffer[Int]()

    queue.enqueue(start)
    visited.add(start)

    while (queue.nonEmpty) {
      val node = queue.dequeue()
      result += node

      graph.get(node) match {
        case Some(neighbors) =>
          for (neighbor <- neighbors if !visited.contains(neighbor)) {
            queue.enqueue(neighbor)
            visited.add(neighbor)
          }
        case None =>
      }
    }

    result.toList
  }

  def main(args: Array[String]): Unit = {
    val graph = Map(
      1 -> List(2, 3),
      2 -> List(4, 5),
      3 -> List(6),
      4 -> List(),
      5 -> List(6),
      6 -> List()
    )

    val startNode = 1
    val result = bfs(graph, startNode)

    println(s"BFS starting from node $startNode : ${result.mkString(" -> ")}")
  }
}

อธิบายโค้ด

ในโค้ดนี้ เราสร้างกราฟขึ้นมาในรูปแบบของ Map โดยใช้ Integer เป็น Node แล้ว List ของ Integer เป็น Node ที่เชื่อมโยงกัน จากนั้นเราใช้ `bfs` ฟังก์ชันในการสำรวจกราฟ จาก Node เริ่มต้น โดยใช้ Queue สำหรับจัดการกับ Node ที่จะทำการสำรวจ และ Set เพื่อเก็บ Node ที่ถูกสำรวจแล้ว

Use Case ในโลกจริง

ลองจินตนาการถึงสถานการณ์ที่เราต้องค้นหาป้อมปราการในเกมส์หรือวิดีโอเกมส์ที่มีโลกเปิด (Open World) อัลกอริธึม BFS ก็สามารถถูกใช้ในการค้นหาว่าเราจะถึงเป้าหมายเมื่ออยู่ที่จุดหนึ่งแล้ว เราสามารถ ค้นหาเส้นทางที่สั้นที่สุดในกราฟที่มีการเชื่อมต่อระหว่างจุดต่าง ๆ

 

วิเคราะห์ Complexity

- Time Complexity: O(V + E) โดย V คือ จำนวน Node และ E คือ จำนวน Edge ในกราฟ - Space Complexity: O(V) เนื่องจากเราต้องใช้ Memory เพื่อเก็บข้อมูลของ Node ที่ถูกเลือกและ Queue ในกระบวนการ BFS

 

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

ข้อดี

- ค้นหาทางสั้นที่สุดในกราฟที่ไม่มีน้ำหนัก: BFS ความเร็วดีเมื่อกราฟไม่มีน้ำหนัก และต้องการหาเส้นทางที่สั้นที่สุด - เข้าใจง่าย: โครงสร้างของ BFS และการทำงานค่อนข้างตรงไปตรงมา ทำให้ศึกษาและเข้าใจได้ง่ายกว่า Algorithm อื่น ๆ

ข้อเสีย

- ใช้พื้นที่มาก: BFS อาจใช้ Memory มากเมื่อกราฟมีขนาดใหญ่ เนื่องจากต้องบันทึก Node ทั้งหมดที่ต้องสำรวจ - ไม่เหมาะกับกราฟน้ำหนัก: BFS จะไม่สามารถหาเส้นทางที่สั้นที่สุดในกราฟที่มีน้ำหนักได้ ถ้าหากน้ำหนักต่างกัน

 

สรุป

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

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

 

 

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