Disjoint Set Union اکتشافی – انجمن DEV

DSU یکی از ظریف ترین در ساختار داده های پیاده سازی است و من بارها در زندگی برنامه نویسی رقابتی خود از آن استفاده کرده ام. اینترنت پر از پیاده سازی های مختلف برای آن است، اما متأسفانه تقریباً هیچ مقاله ای وجود ندارد که اثبات خوبی برای کارایی DSU داشته باشد، در این مقاله به بهترین نحو این راز را کشف خواهم کرد.

ساختار داده Trivial Disjoint Set Union را می توان به روش زیر پیاده سازی کرد

class DSU 
{
    private int[] parent;

    void createSet(int vertex)
    {
        parent[vertex] = vertex;
    } 

    bool isRepresentative(int vertex)
    {
        return parent[vertex] == vertex;
    }

    void findRepresentative(int vertex)
    {
        if (!isRepresentative(vertex))
        {
            return findRepresentative(parent[vertex]);
        }

        return vertex;
    } 


    void mergeSets(int lhs, int rhs)
    {
        int rhsRepresentative = findRepresentative(rhs);
        int lhsRepresentative = findRepresentative(lhs);

        if (lhsRepresentative != rhsRepresentative)
        {
            parent[lhsRepresentative] = rhsRepresentative;
        }
    }
}

بیایید با دو DSU اکتشافی بی اهمیت شروع کنیم

اکتشافی رتبه عمق درخت

اکتشافی زیر نشان می دهد که ما باید یک مجموعه درخت با عمق کمتر را به درخت مجموعه با عمق بیشتر متصل کنیم.

void createSet(int vertex) 
{
    parent[vertex] = vertex;
    rank[vertex] = 1;
}

void mergeSets(int lhs, int rhs)
{
    int rhsRepresentative = findRepresentative(rhs);
    int lhsRepresentative = findRepresentative(lhs);

    if (rhsRepresentative != lhsRepresentative)
    {
        if (rank[lhsRepresentative] < rank[rhsRepresentative]) 
        {
            swap(lhsRepresentative, rhsRepresentative);
        }

        parent[rhsRepresentative] = lhsRepresentative;
        if (depth[lhsRepresentative] == depth[rhsRepresentative]) 
        {
            rank[lhsRepresentative] += 1;
        }
    }
}

بیایید نشان دهیم که این اکتشافی به کاهش پیچیدگی findRepresentative به O(log(N)) کمک خواهد کرد.

ما می توانیم این کار را با اثبات اینکه اگر rank set-tree برابر با K باشد، این درخت حداقل دارای 2^K رئوس و دارای عمق K است. از القاء روی K استفاده خواهیم کرد.

اگر K = 1 باشد، اندازه درخت 1 و عمق آن 1 است.

بیایید درک کنیم که چگونه یک مجموعه درخت با رتبه برابر K به دست می آوریم. اگر دو مجموعه درخت از رتبه های K-1 یکسان را ادغام کنیم این اتفاق می افتد. اما می دانیم که برای درختان مجموعه با رتبه K-1، عمق K-1 داریم، به این معنی است که یک مجموعه درخت جدید برای رتبه K حداقل شامل 2 * 2^(K – 1) = 2^K خواهد بود. رئوس و دارای عمق حداکثر K هستند.

اکتشافی رتبه بندی اندازه درخت

اکتشافی مشابه، اما پیشنهاد می‌کند که یک مجموعه کوچک‌تر را به درخت بزرگ‌تر متصل کنید.

void createSet(int vertex) 
{
    parent[vertex] = vertex;
    size[vertex] = 1;
}

void mergeSets(int lhs, int rhs)
{
    int rhsRepresentative = findRepresentative(rhs);
    int lhsRepresentative = findRepresentative(lhs);

    if (rhsRepresentative != lhsRepresentative)
    {
        if (size[lhsRepresentative] < size[rhsRepresentative]) 
        {
            swap(lhsRepresentative, rhsRepresentative);
        }

        parent[rhsRepresentative] = lhsRepresentative;
        size[lhsRepresentative] += size[rhsRepresentative];
    }
}

به روشی مشابه می توانیم ثابت کنیم که اگر اندازه درخت مجموعه K باشد، ارتفاع آن log(K) است.

اگر K = 1 باشد، واضح است که درست است.

بیایید به دو درخت Tree_k1 با اندازه k1 و Tree_k2 با اندازه k2 نگاه کنیم. می توان گفت که Tree_k1 دارای log ارتفاع (k1) و Tree_k2 دارای log ارتفاع (k2) است.

فرض کنید k1 >= k2، سپس Tree_k2 به Tree_k1 متصل می شود و ارتفاع جدید درخت max(log(k1)، log(k2) + 1 خواهد بود.

اکنون بسیار آسان است که نشان دهیم ارتفاع جدید h کوچکتر از log (k1 + k2) است.

حالا بیایید نگاهی به اکتشافی کمی جالب‌تر بیندازیم

اکتشافی فشرده سازی مسیر درختی

بیایید بهینه سازی زیر تابع findRepresentative را در نظر بگیریم

public int findRepresentative(int vertex)
{
    if (!isRepresentative(vertex)) 
    {
        parent[vertex] = findRepresentative(
            parent[vertex]
        );
    }

    return parent[vertex];
}

در این کد ما تمام لبه های یک مسیر را حذف می کنیم vertex به ریشه (نماینده) رئوس اتصال درخت مجموعه در مسیر به ریشه.

مشاهده اول، اینکه این به تنهایی می تواند درختی با عمق O(N) تولید کند. برای این کار ما همیشه ریشه یک set-tree را به یک مجموعه درخت یک راس متصل می کنیم.

در تصویر بالا findRepresentative همیشه برای ریشه set-tree فراخوانی می شود، بنابراین پیچیدگی این فراخوانی O(1) است.

بیایید موردی را در نظر بگیریم که findRepresentative از ریشه غیر set-tree فراخوانی شود و بفهمیم که چرا به طور متوسط ​​پیچیدگی O(log N) دارد. برای انجام این کار، اجازه می‌دهیم با معرفی یک دسته برای لبه‌های درخت مجموعه شروع کنیم.

حاشیه، غیرمتمرکز (الف، ب) جایی که آ پدر و مادر است ب دسته بندی دارد 2^K اگر 2^K <= اندازه(a) - اندازه(ب) <2^(K + 1).

بیایید به مسیری که هنگام تماس حذف می شود نگاه کنیم findRepresentative(x) (با رنگ زرد مشخص شده است)

اگر این مسیر دارای لبه های log(N) باشد، ما از آن راضی هستیم زیرا می خواهیم پیچیدگی O(log N) را اثبات کنیم.

فرض کنید لبه های بیش از log(N) وجود دارد. در این حالت حداقل دو یال با همان دسته K (
اصل کبوتر)

بیایید تعریف کنیم اندازه (a/b) به اندازه اندازه درخت فرعی آ بدون درخت فرعی از ب.

ما به راحتی می توانیم اندازه (u / v) >= 2^K + size(v) و size(a/b) >= 2^K + size(b) را ببینیم. اما می توانیم بیشتر بگوییم! v در زیر درخت خود حداقل رئوس اندازه (a / b) را شامل می شود، به این معنی که اندازه (u / v) >= اندازه (a / b) + 2^K >= اندازه (b) + 2^K + 2 ^ ک.

بیایید با دقت بیشتری به اولین لبه دسته 2^K در مسیر نگاه کنیم. با مشاهده بالا می توانیم بفهمیم که دسته یال (R, v) که به جای (u, v) به عنوان بخشی از فشرده سازی مسیر اضافه می کنیم چه خواهد بود. اندازه درخت فرعی R حداقل اندازه (u / v) + اندازه (v) است که بیش از 2^ (K + 1) + اندازه (v) است و اندازه v اندازه (v) است، بنابراین اندازه ( R/V) >= 2^(K + 1). این به این معنی است که اگر در مسیری از نماینده (R) تا راس x بیشتر از log(N) یال وجود داشته باشد، حداقل در لبه با دسته افزایش وجود خواهد داشت. این دسته با اندازه درخت محدود می شود بنابراین نمی تواند به طور نامحدود رشد کند.

بیایید نشان دهیم که وقتی یک یال را در مسیر با لبه ای به ریشه جایگزین می کنیم، دسته آن یال نمی تواند کاهش یابد. فرض کنید که یال (u, v) را با یال (R, v) جایگزین می کنیم. از آنجایی که R یکی از اجداد u است، حداقل یک راس بیشتر در زیر درخت خود خواهد داشت، بنابراین اندازه (u, v) < size(R, v) + 1.

همه یال‌های دیگر دسته‌بندی خود را تغییر نمی‌دهند، زیرا جایگزینی یال بر آنها تأثیر نمی‌گذارد یا اندازه هر دو راس آن یال به همان تعداد کاهش می‌یابد.

بنابراین با دانستن اینکه دسته یال‌ها فقط در حال رشد هستند و محدودیت دارند، می‌توان گفت که بیشتر از (N – 1) * log(N) نخواهد بود (هر یال در مجموعه درخت با اندازه N حداکثر می‌تواند دسته خود را افزایش دهد. ورود به سیستم (N)). با ترکیب با سناریویی که مسیر از یک راس به نماینده کمتر یا مساوی با log (N) است، پیچیدگی کل را برای عملیات M به دست آوردیم findRepresentative O((M + N)log(N)).

ترکیب فشرده سازی مسیر با اکتشافی رتبه

اثبات این امر نسبتاً پیچیده است، اما من معتقدم لازم به ذکر است که پیچیدگی این اکتشافی، الگوریتم را به O(ackermann(n)) سرعت می بخشد، که در آن آکرمن تابع آکرمن معکوس است که رشد بسیار کندی دارد (به عنوان مثال برای n <= 10). ^500، ackermann(n) < 4).

خلاصه

در این مقاله نگاهی به یک ساختار داده جذاب DSU انداختیم و رایج‌ترین اکتشافی‌های مورد استفاده در آن را ثابت کردیم و یک اکتشافی بسیار کارآمد را ذکر کردیم که دو مورد از آنها را ترکیب می‌کند.