ค้นหาแบบกว้างด้วย Breadth-First Search (BFS) ใน Java

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

อัลกอริทึม Breadth-First Search คืออะไร?

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

การใช้งาน BFS ในภาษา Java

import java.util.*;

public class BFSExample {
    private int V;   // จำนวนโหนดในกราฟ
    private LinkedList adj[]; // รายการอ้างอิงของแต่ละโหนด

    // Constructor
    BFSExample(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i=0; i queue = new LinkedList(); // Create a queue for BFS

        visited[s] = true; // Mark the current node as visited and enqueue it
        queue.add(s);

        while (queue.size() != 0) {
            // Dequeue a vertex from queue and print it
            s = queue.poll();
            System.out.print(s+" ");

            // Get all adjacent vertices of the dequeued vertex s
            // If a adjacent has not been visited, then mark it visited and enqueue it
            Iterator i = adj[s].listIterator();
            while (i.hasNext()) {
                int n = i.next();
                if (!visited[n]) {
                    visited[n] = true;
                    queue.add(n);
                }
            }
        }
    }

    // Driver method to
    public static void main(String args[]) {
        BFSExample g = new BFSExample(4);

        g.addEdge(0, 1);
        g.addEdge(0, 2);
        g.addEdge(1, 2);
        g.addEdge(2, 0);
        g.addEdge(2, 3);
        g.addEdge(3, 3);

        System.out.println("Following is Breadth First Traversal "+
                           "(starting from vertex 2)");

        g.BFS(2);
    }
}

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

Usecase ของ BFS ในโลกจริง

BFS มีการใช้งานที่หลากหลายในโลกจริง เช่น

- Social Networking - ในเครือข่ายสังคมเช่น Facebook หรือ LinkedIn, BFS ใช้ในการหา 'เพื่อนแนะนำ' หรือ 'การเชื่อมต่อระดับแรก' ของโปรไฟล์. 

- GPS Navigation Systems - ในระบบนำทาง เช่น Google Maps, BFS ใช้ในการหาเส้นทางที่สั้นที่สุดระหว่างจุดเริ่มต้นและปลายทาง.

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

Complexity

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

ข้อดี

- การค้นหาสั้นที่สุด - BFS มีประโยชน์ในการหาเส้นทางที่สั้นที่สุดจากโหนดหนึ่งไปยังโหนดอื่น. 

- ไม่ต้องใช้ Recursion - การใช้ Queue ใน BFS หมายความว่าวิธีการใช้งานไม่ต้องอาศัยการเรียกตัวเองซ้ำ (recursion).

ข้อเสีย

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

- การค้นหาอาจเป็นไปอย่างช้า - ถ้ากราฟมีความหนาแน่นของ edges มาก BFS อาจทำการค้นหาได้ช้าเนื่องจากต้องสำรวจให้ทั่ว.

การเรียนรู้ Algorithm อย่าง BFS จะช่วยเสริมทักษะในการคิดวิเคราะห์และแก้ไขปัญหาต่างๆ ถ้าคุณสนใจในการพัฒนาความรู้ด้านการเขียนโปรแกรม เชิญที่ [Expert-Programming-Tutor](#) ที่พร้อมจะเป็นตัวช่วยให้คุณได้บรรลุเป้าหมายในโลกของการเขียนโปรแกรม!

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