Disjoint Set (Union-Find Algorithm) ใน PHP

ที่ตีพิมพ์: 16 กุมภาพันธ์ 2025 เวลา 12 นาฬิกา 28 นาที 33 วินาที UTC
ปรับปรุงล่าสุด : 26 มกราคม 2026 เวลา 10 นาฬิกา 37 นาที 02 วินาที UTC

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

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

Disjoint Set (Union-Find Algorithm) in PHP

ชุดที่ไม่ต่อเนื่อง (ใช้กันทั่วไปสําหรับ 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 เหมือนกัน

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