Disjoint Set (Union-Find Algorithm) ใน PHP

ที่ตีพิมพ์: 16 กุมภาพันธ์ 2025 เวลา 12 นาฬิกา 28 นาที 33 วินาที UTC

บทความนี้นําเสนอการใช้งาน PHP ของโครงสร้างข้อมูล Disjoint Set ซึ่งมักใช้สําหรับ Union-Find ในอัลกอริทึมต้นไม้สแปนนิ่งขั้นต่ํา

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

Disjoint Set (Union-Find Algorithm) in PHP

Disjoint Set (โดยทั่วไปจะใช้สําหรับ Union-Find หรือที่เรียกว่า Disjoint Set Union) เป็นโครงสร้างข้อมูลที่ใช้ในการจัดการพาร์ติชันขององค์ประกอบเป็นชุดที่ไม่ต่อเนื่อง (ไม่ทับซ้อนกัน) รองรับการดําเนินการหลักสองอย่างอย่างมีประสิทธิภาพ:

ค้นหา: กําหนดว่าองค์ประกอบเป็นของชุดใด
สหภาพ: รวมสองชุดเข้าด้วยกัน

โครงสร้างนี้มีประโยชน์อย่างยิ่งในอัลกอริทึมต้นไม้สแตนนิ่งขั้นต่ํา เช่น อัลกอริทึมของ Kruskal

ฉันมีการใช้งานอัลกอริทึมของ Kruskal ที่ใช้สําหรับการสร้างเขาวงกตแบบสุ่มซึ่งอาศัยการใช้งาน PHP ด้านล่างของ Disjoint Set เพื่อรวมชุดอย่างมีประสิทธิภาพ หากคุณสนใจ คุณสามารถดูการใช้งานจริงได้ที่นี่: เครื่องกําเนิดเขาวงกตอัลกอริทึมของ Kruskal

อย่างไรก็ตามนี่คือการใช้งาน PHP ของฉันของ Disjoint Set:

class DisjointSet 
{
    private $parent = [];
    private $rank   = [];

    public function __construct($size) 
    {
        for ($i = 0; $i < $size; $i++) 
        {
            $this->parent[$i]   = $i;
            $this->rank[$i]     = 0;
        }
    }

    public function find($x) 
    {
        if ($this->parent[$x] != $x) 
        {
            $this->parent[$x] = $this->find($this->parent[$x]);
        }

        return $this->parent[$x];
    }

    public function union($x, $y) 
    {
        $rootX = $this->find($x);
        $rootY = $this->find($y);

        if ($rootX != $rootY) 
        {
            if ($this->rank[$rootX] > $this->rank[$rootY]) 
            {
                $this->parent[$rootY] = $rootX;
            }
            elseif ($this->rank[$rootX] < $this->rank[$rootY]) 
            {
                $this->parent[$rootX] = $rootY;
    
            }
            else
            {
                $this->parent[$rootY] = $rootX;
                $this->rank[$rootX]++;
            }
        }
    }
}

นอกเหนือจากการสร้างเขาวงกตเพื่อความสนุกสนานแล้ว โครงสร้างข้อมูล Disjoint Set ยังสามารถใช้สําหรับสถานการณ์ในชีวิตจริงได้อีกด้วย

ตัวอย่างเช่น ลองนึกภาพโซเชียลเน็ตเวิร์กที่ต้องการแนะนําเพื่อนใหม่ให้กับผู้ใช้ แล้วสมมติว่าเรามีคนหกคนที่มีความสัมพันธ์กับเพื่อนเหล่านี้อยู่แล้ว:

1 และ 2 เป็นเพื่อนกัน
2 และ 3 เป็นเพื่อนกัน
4 และ 5 เป็นเพื่อนกัน
6 ไม่มีเพื่อน

การใช้อัลกอริทึม Union-Find กับกลุ่มที่แยกจากกันเหล่านี้ เราควรพบสิ่งต่อไปนี้:

1, 2 และ 3 ในกลุ่มเดียว
4 และ 5 ในกลุ่มที่สอง
6 ในกลุ่มที่สาม

ด้วยเหตุนี้ จึงสมเหตุสมผลที่จะแนะนําว่า 1 และ 3 ควรเป็นเพื่อนกัน เพราะพวกเขามีบุคคลที่ 2 เหมือนกัน

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