การทำความรู้จักกับ Breadth First Search (BFS) ในภาษา PHP

อะไรคือ Breadth First Search (BFS)?

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

แก้ปัญหาอะไรได้บ้าง?

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

ตัวอย่างโค้ด BFS ด้วยภาษา PHP

เราจะมาใช้ BFS ในการค้นหาเส้นทางจากโหนดหนึ่งไปยังโหนดหนึ่ง ในตัวอย่างนี้เราจะสร้างกราฟเล็ก ๆ แล้วค้นหาทางไปยังโหนดที่กำหนด

 <?php

class Graph {
    private $adjacencyList;

    public function __construct() {
        $this->adjacencyList = [];
    }

    public function addEdge($source, $destination) {
        if (!array_key_exists($source, $this->adjacencyList)) {
            $this->adjacencyList[$source] = [];
        }
        $this->adjacencyList[$source][] = $destination;
    }

    public function bfs($startNode, $endNode) {
        $visited = [];
        $queue = [];

        $queue[] = $startNode;
        $visited[$startNode] = true;

        while (!empty($queue)) {
            $currentNode = array_shift($queue);
            echo "Visiting: " . $currentNode . "\n";

            // If we found the destination
            if ($currentNode === $endNode) {
                return true;
            }

            foreach ($this->adjacencyList[$currentNode] ?? [] as $neighbor) {
                if (!isset($visited[$neighbor])) {
                    $visited[$neighbor] = true;
                    $queue[] = $neighbor;
                }
            }
        }

        return false;
    }
}

// การใช้งาน
$graph = new Graph();
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'D');
$graph->addEdge('C', 'D');
$graph->addEdge('D', 'E');

$start = 'A';
$end = 'E';
if ($graph->bfs($start, $end)) {
    echo "Path found from $start to $end\n";
} else {
    echo "No path found from $start to $end\n";
}
?>

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

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

ข้อดี

- สามารถค้นหาเส้นทางสั้นที่สุดในกราฟที่ไม่มีน้ำหนักได้

- ใช้งานง่าย และเข้าใจได้ง่าย

ข้อเสีย

- ใช้หน่วยความจำมากในกราฟใหญ่

- ไม่สามารถทำงานได้ดีในกราฟที่มีน้ำหนัก

Use Case ในโลกจริง

หนึ่งใน use case ที่เด่นชัดคือการใช้งาน BFS ในการค้นหาสิ่งที่ใกล้เคียงที่สุดในโซเชียล เน็ตเวิร์ค เช่น ต้นไม้สังคม ที่เราสามารถใช้ BFS เพื่อค้นหาเพื่อนของเพื่อนและค้นหาความเชื่อมโยงระหว่างผู้คนในสังคม

ยกตัวอย่างเช่น ถ้าคุณต้องการค้นหาความสัมพันธ์ใน LinkedIn คุณอาจจะเริ่มจากโปรไฟล์ของคุณเองและใช้ BFS เพื่อสำรวจคำเชื่อมโยงของเพื่อน ๆ ของคุณ เพื่อนของเพื่อน และอื่น ๆ เพื่อค้นหาความสัมพันธ์ที่มีศักยภาพในการทำงานร่วมกัน

สรุป

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

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

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