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

 

การศึกษาโปรแกรมมิ่งไม่เพียงแต่ช่วยให้เราเขียนโปรแกรมที่ดี แต่ยังช่วยให้เราเข้าใจแนวทางการแก้ปัญหาที่ซับซ้อนได้ในหลาย ๆ สาขา หนึ่งในอัลกอริธึมที่สำคัญที่นักพัฒนาและนักวิจัยคอมพิวเตอร์ต้องรู้จักคือ **Breadth First Search (BFS)** หรือ **การค้นหากว้าง** ในบทความนี้ เราจะพูดถึง BFS ว่าคืออะไร ทำงานอย่างไร ใช้แก้ปัญหาอะไร และจะมีตัวอย่างโค้ดในภาษา Dart รวมทั้งวิจารณ์ความสามารถและข้อจำกัดของมัน

 

BFS คืออะไร?

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

ขอบเขตการใช้งานของ BFS

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

- การค้นหาเส้นทางในเกมหรือกราฟ

- ระบบเครือข่าย เช่น การค้นหาข้อมูลใน Social Network

- การสำรวจอัลกอริธึมต่างๆ ในวิทยาศาสตร์ข้อมูล

 

ตัวอย่างโค้ดการค้นหากว้างในภาษา Dart

ให้เรามาดูตัวอย่างการเขียน BFS ด้วยภาษา Dart กัน โดยจะใช้โครงสร้างข้อมูลแบบกราฟ (Graph) เป็นตัวอย่าง

 import 'dart:collection';

class Graph {
  Map<int, List<int>> adjList = {};

  void addEdge(int u, int v) {
    if (!adjList.containsKey(u)) {
      adjList[u] = [];
    }
    if (!adjList.containsKey(v)) {
      adjList[v] = [];
    }
    adjList[u]!.add(v);
    adjList[v]!.add(u); // เป็นกราฟสองทาง
  }

  void bfs(int start) {
    Queue<int> queue = Queue<int>();
    Set<int> visited = Set();

    queue.add(start);
    visited.add(start);

    while (queue.isNotEmpty) {
      int current = queue.removeFirst();
      print("Visited: $current");

      for (int neighbor in adjList[current]!) {
        if (!visited.contains(neighbor)) {
          visited.add(neighbor);
          queue.add(neighbor);
        }
      }
    }
  }
}

void main() {
  Graph g = Graph();
  g.addEdge(1, 2);
  g.addEdge(1, 3);
  g.addEdge(2, 4);
  g.addEdge(3, 5);

  print("Breadth First Search starting from vertex 1:");
  g.bfs(1);
}

ในตัวอย่างข้างต้น เรามีกราฟที่ประกอบด้วย 5 จุด (1-5) และเชื่อมโยงระหว่างกันโดยใช้ `addEdge` ฟังก์ชัน เราใช้ `Queue` เพื่อทำการเก็บค่าที่ต้องการสำรวจและ `Set` เพื่อติดตามตำแหน่งที่เราได้เข้าชมไปแล้ว โปรแกรมจะเริ่มจากจุดเริ่มต้น (vertex 1) และจะเยี่ยมชมจุดเชื่อมต่อทั้งหมดย่อยจนกว่าจะสำเร็จ!

 

Use Cases ในโลกจริง

1. การค้นหาสิ่งที่ใกล้เคียงกันใน Social Network: หลาย ๆ แอปพลิเคชันโซเชียลมีเดียสามารถใช้ BFS เพื่อค้นหาเพื่อนที่เป็นไปได้ในการเชื่อมโยงกันซึ่งอยู่ใกล้ที่สุด

2. การค้นหาเส้นทางใน Google Maps: BFS เป็นเครื่องมือที่ช่วยในการสำรวจเส้นทางที่สั้นที่สุดในผู้ใช้เลือกเดินทางโดยใช้อัลกอริธึมนี้

3. การจัดการและติดตามปัญหาที่เกิดขึ้นในระบบการเครือข่าย: BFS จะช่วยให้เราสามารถติดตามการเกิดปัญหาจากต้นเหตุไปยังปัญหาที่เกิดขึ้น ได้อย่างมีประสิทธิภาพ

 

การวิเคราะห์ Complexity

1. Time Complexity: ความยากในการดำเนินการ BFS ดังนี้

- O(V + E) โดยที่ V คือจำนวนของจุด (vertices) และ E คือจำนวนขอบ (edges) ในกราฟ

- อัลกอริธึมนี้จะใช้เวลาในการเยี่ยมชมทุกจุดและการเดินทางผ่านทุกขอบพันธุ์

2. Space Complexity:

- O(V) เป็นพื้นที่ที่ใช้ในการเก็บค่า visited และ queue

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

#### ข้อดี:

- ค้นหาได้ในระดับกว้างๆ ทำให้พบเส้นทางที่สั้นที่สุดถ้ามี

- ทำความเข้าใจได้ง่าย และพึ่งพาโครงสร้างข้อมูลง่ายๆ

#### ข้อเสีย:

- ใช้พื้นที่หน่วยความจำมากในกราฟที่หนาแน่นหรือมีจุดที่มาก

- อาจจะไม่เร็วในขกราฟที่มีระดับลึกมาก

 

สรุป

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

เข้าร่วมกับเราได้เลยที่ EPT และเริ่มการเดินทางในการเป็นนักพัฒนาที่เก่งกว่าเดิม!

 

 

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