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

یک روش ساده برای ساختن این داده ساختار به این شکل است که برای هر مجموعه، یک لیست پیوندی تشکیل دهیم و عنصر ابتدای هر لیست را به عنوان نماینده آن مجموعه انتخاب کینم. تابع ایجاد مجموعه، یک لیست جدید با یک عنصر را می‌سازد. تابع ادغام، لیست دو مجموعه را به هم پیوند می‌دهد، که زمان ثابتی می‌گیرد. مشکل این روش پیاده‌سازی در تابع جستجو است که به زمان Ω(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 یک تابع کند دیگر (اما نه به کندی معکوس تابع اکرمن) بود.

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

• ویکی‌پدیای انگلیسی
• سایت تاپ کدر
• قدسی، محمد، داده ساختارها و مبانی الگوریتم‌ها. تهران: انتشارات فاطمی، ۱۳۸۸.

• نظریه گراف‌ها
• ساختمان داده
• مجموعه‌های مجزا

• پیاده‌سازی با ++C و #C
• پیاده‌سازی با ++C
• پیاده‌سازی با جاوا
• جاوا اپلت، پیاده‌سازی گرافیکی
• پیاده‌سازی با پایتون