مجموعه‌های مجزا (ساختمان داده)

فرض کنید مجموعه تاریخی‌ای از عناصر را در اختیار داریم. گاهی از مواقع می‌خواهیم آن‌ها را به چند مجموعه بدون اشتراک افراز کنیم. داده ساختار مجموعه‌های مجزا، داده ساختاری است که این کار را انجام می‌دهد. یک الگوریتم جستجو-ادغام، الگوریتمی است که دو عمل زیر را روی این داده ساختار انجام می‌دهد:

  • جستجو: مشخص می‌کند که یک عنصر در کدام مجموعه قرار دارد. همچنین می‌تواند مشخص کند که آیا دو عنصر در یک مجموعه قرار دارند یا نه.
  • ادغام: دو مجموعه را با هم ادغام می‌کند و یک مجموعه جدید می‌سازد.

عملیات مهم دیگری هم که روی این داده ساختار انجام می‌شود، ایجاد مجموعه است که یک مجموعه جدید شامل یک عضو داده شده را ایجاد می‌کند که عموماً بسیار ساده‌است. با در اختیار داشتن این ۳ عمل، می‌توان بسیاری از مسائل تقسیم‌بندی را حل کرد. برای این که این ۳ عمل را با دقت تعریف کنیم، روشی برای مشخص کردن مجموعه‌ها لازم است. یک روش معمول برای این کار این است که برای هر مجموعه، یک عضو مشخص از آن را انتخاب کنیم و آن را نماینده این مجموعه بنامیم. در این صورت، تابع جستجو برای یک عضو، نماینده مجموعه‌ای که این عضو در آن قرار دارد را برمی‌گرداند و تابع ادغام نماینده دو مجموعه را به عنوان ورودی می‌گیرد.

پیاده‌سازی با لیست پیوندی

یک روش ساده برای ساختن این داده ساختار به این شکل است که برای هر مجموعه، یک لیست پیوندی تشکیل دهیم و عنصر ابتدای هر لیست را به عنوان نماینده آن مجموعه انتخاب کینم. تابع ایجاد مجموعه، یک لیست جدید با یک عنصر را می‌سازد. تابع ادغام، لیست دو مجموعه را به هم پیوند می‌دهد، که زمان ثابتی می‌گیرد. مشکل این روش پیاده‌سازی در تابع جستجو است که به زمان Ω(n) احتیاج دارد. می‌توان با اضافه کردن یک اشاره گر به هر گره در لیست‌ها که به ابتدای آن لیست اشاره می‌کند، این مشکل را رفع کرد. اما حالا تابع ادغام باید این اشاره گر تمام گره‌های یک لیست که به لیست دیگری چسبانده می‌شود را به روز کند، پس این تابع به زمان (Ω(n احتیاج دارد. اگر طول هر لیست را نگه داریم، و در هر مرحله لیست کوچکتر را به لیست بزرگتر بچسبانیم، می‌توان زمان را بهبود داد. در این صورت اگر از m تابع جستجو، ادغام و ایجاد مجموعه روی n عضو اعمال شوند، زمان(O(m + n log n مصرف می‌شود.

پیاده‌سازی به وسیله جنگل‌ها

در این پیاده‌سازی هر مجموعه به وسیله یک درخت نشان داده می‌شود که هر گره در آن یک اشاره‌گر به پدرش دارد. این پیاده‌سازی ابتدا توسط برنارد ای. گالر و مایکل جی. فیشر در سال ۱۹۶۴ پیشنهاد شد، البته تحلیل زمانی دقیق آن تا مدت‌ها طول کشید. در این روش، نماینده هر مجموعه، ریشه درخت آن مجموعه انتخاب می‌شود. تابع جستجو، پدران یک راس را تا جایی دنبال می‌کند که به ریشه درخت برسد و تابع ادغام، ریشه یک درخت را به ریشه درخت دیگر متصل می‌کند تا یک درخت به وجود بیاید. یکی از روش‌های پیاده‌سازی می‌تواند به شکل زیر باشد:

function MakeSet(x)
     x.parent:= x

function Find(x)
     if x.parent == x
        return x
     else
        return Find(x.parent)

function Union(x, y)
     xRoot:= Find(x)
     yRoot:= Find(y)
     xRoot.parent:= yRoot

در این پیاده‌سازی ساده، این روش بهتر از روش پیاده‌سازی با لیست‌های پیوندی نیست، زیرا درختی که ساخته می‌شود، می‌تواند کاملاً نامتوازن باشد، اما به دو روش می‌توان این پیاده‌سازی را بهبود داد.

روش اول که ادغام بر حسب مرتبه نام دارد، به این صورت است که همیشه ریشه درخت کوچکتر را به ریشه درخت بزرگتر وصل می‌کنیم. از آن جا که زمان اجرا به عمق درخت وابسته‌است، درخت با عمق کمتر زیر درخت با عمق بیشتر قرار می‌گیرد که فقط در صورتی که عمق‌ها برابر باشند، عمق درخت حاصل افزایش میابد. در این الگوریتم به به جای عمق از واژه مرتبه استفاده می‌شود، زیرا اگر از فشرده سازی مسیر(در ذیل توضیح داده خواهد شد) هم استفاده کنیم، دیگر مرتبه برابر با عمق درخت نخواهد بود. تعریف می‌کنیم که درخت‌های تک عضوی دارای مرتبه صفر هستند و در هر مرحله که دو درخت دارای مرتبه برابر r باشند، درخت حاصل از ادغام آن‌ها دارای مرتبه r+۱ خواهد بود. تنها پیاده کردن این تکنیک باعث می‌شود که زمان عملیات‌های جستجو، ادغام و ایجاد مجموعه به‌طور سرشکن برابر (O(log n باشد. کد ارتقا یافته برای توابع جستجو و ایجاد مجموعه:

function MakeSet(x)
     x.parent:= x
     x.rank:= 0

function Union(x, y)
     xRoot:= Find(x)
     yRoot:= Find(y)
     if xRoot.rank> yRoot.rank
         yRoot.parent:= xRoot
     else if xRoot.rank <yRoot.rank
         xRoot.parent:= yRoot
     else if xRoot!= yRoot// Unless x and y are already in same set, merge them
         yRoot.parent:= xRoot
         xRoot.rank:= xRoot.rank + 1

تکنیک بعدی که فشرده‌سازی مسیر نام دارد، روشی است که ساختمان درخت را در هر مرحله که جستجو روی آن انجام می‌شود، کم عمق تر می‌کند. ایده این است که هر راسی که در مسیر به راس ریشه وجود دارد، می‌تواند به صورت مستقیم به ریشه متصل شود، زیرا همه این رئوس یک نماینده مشترک دارند. برای پیاده کردن این تکنیک، در هنگامی که جستجو به صورت بازگشتی از رئوس درخت به سمت ریشه حرکت می‌کند، پدر هر راس را برابر ریشه‌ای قرار می‌دهد که پیدا کرده‌است. درخت حاصل کم عمق تر از درخت اولیه‌است که باعث سریع تر شدن عملیات‌ها روی این رئوس و نوادگان آن‌ها می‌شود. کد ارتقا یافته تابع جستجو:

function Find(x)
     if x.parent == x
        return x
     else
        x.parent:= Find(x.parent)
        return x.parent

این دو تکنیک همدیگر را کامل می‌کنند، اگر هر دو با هم انجام بشوند، زمان سر شکن شده برای هر عملیات از ((O(α(n می‌شود که (α(n معکوس تابع (f(n) = A(n,n است و A تابع اکرمن است که بسیار سریع رشد می‌کند. چون (α(n معکوس این تابع است، (α(n برای تمامی مقادیر کاربردی n کمتر از ۵ است؛ بنابراین زمان سرشکن شده برای هر عملیات یک ثابت کوچک است.

کاربردها

داده ساختار مجموعه‌های مستقل، تقسیم‌بندی یک مجموعه را مدل می‌کند، به عنوان مثال نگه داشتن مولفه‌های همبندی یک گراف بی‌جهت را می‌توان با این داده ساختار مدل کرد. این مدل می‌تواند برای بررسی کردن این که آیا دو راس در یک مؤلفه قرار دارند یا این که آیا اضافه کردن یال بین آن‌ها می‌تواند یک دور ایجاد کند، به کار برود.

این مدل در پیاده‌سازی الگوریتم کروسکال برای پیدا کردن زیر درخت فراگیر با کمترین وزن در یک گراف نیز به کار می‌رود.

توجه کنید که ساختمان داده مجموعه‌های مجزا اجازه حذف یال‌ها را (حتی در صورتی که از دغام بر حسب مرتبه و فشرده سازی مسیر استفاده نکنیم) نمی‌دهد. البته روشهای پیچیده تری برای کار با این عملیات‌ها طراحی شده‌اند.

تاریخچه

با وجود اینکه ایده‌های مجموعه‌های مجزا برای مدت‌ها مورد استفاده قرار می‌گرفت، رابرت تارژان اولین کسی بود که کران بالای این مسئله که برابر معکوس تابع اکرمن می‌باشد را در سال ۱۹۷۵ به دست آورد. تا قبل از این زمان، بهترین کران برابر (O(log * n یک تابع کند دیگر (اما نه به کندی معکوس تابع اکرمن) بود.

همچنین تارژان و فنلیوون یک الگوریتم یکبار اجرا را طراحی کردند که در عمل، کارا تر است اما در بدترین حالت، دو الگوریتم دارای پیچیدگی زمانی برابری هستند.

منابع

    جستارهای وابسته

    پیوند به بیرون
    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.