موضوع مقاله: مجموعه‌های مجزا (ساختمان داده) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مجموعه‌های مجزا (ساختمان داده) | مقدمه: یک الگوریتم جستجو-ادغام، الگوریتمی است که دو عمل زیر را روی این داده ساختار انجام می‌دهد: جستجو: مشخص می‌کند که یک عنصر در کدام مجموعه قرار دارد. | ## بخش 1: مجموعه‌های مجزا (ساختمان داده) | عملیات مهم دیگری هم که روی این داده ساختار انجام می‌شود، ایجاد مجموعه است که یک مجموعه جدید شامل یک عضو داده شده را ایجاد می‌کند که عموماً بسیار ساده‌است. برای این که این ۳ عمل را با دقت تعریف کنیم، روشی برای مشخص کردن مجموعه‌ها لازم است. یک روش معمول برای این کار این است که برای هر مجموعه، یک عضو مشخص از آن را انتخاب کنیم و آن را نماینده این مجموعه بنامیم. در این صورت، تابع جستجو برای یک عضو، نماینده مجموعه‌ای که این عضو در آن قرار دارد را برمی‌گرداند و تابع ادغام نماینده دو مجموعه را به عنوان ورودی می‌گیرد. پیاده‌سازی با لیست پیوندی یک روش ساده برای ساختن این داده ساختار به این شکل است که برای هر مجموعه، یک لیست پیوندی تشکیل دهیم و عنصر ابتدای هر لیست را به عنوان نماینده آن مجموعه انتخاب کینم. می‌توان با اضافه کردن یک اشاره گر به هر گره در لیست‌ها که به ابتدای آن لیست اشاره می‌کند، این مشکل را رفع کرد. اما حالا تابع ادغام باید این اشاره گر تمام گره‌های یک لیست که به لیست دیگری چسبانده می‌شود را به روز کند، پس این تابع به زمان (Ω(n احتیاج دارد. اگر طول هر لیست را نگه داریم، و در هر مرحله لیست کوچکتر را به لیست بزرگتر بچسبانیم، می‌توان زمان را بهبود داد. | ## بخش 2: مجموعه‌های مجزا (ساختمان داده) | پیاده‌سازی به وسیله جنگل‌ها در این پیاده‌سازی هر مجموعه به وسیله یک درخت نشان داده می‌شود که هر گره در آن یک اشاره‌گر به پدرش دارد. تابع جستجو، پدران یک راس را تا جایی دنبال می‌کند که به ریشه درخت برسد و تابع ادغام، ریشه یک درخت را به ریشه درخت دیگر متصل می‌کند تا یک درخت به وجود بیاید. روش اول که ادغام بر حسب مرتبه نام دارد، به این صورت است که همیشه ریشه درخت کوچکتر را به ریشه درخت بزرگتر وصل می‌کنیم. از آن جا که زمان اجرا به عمق درخت وابسته‌است، درخت با عمق کمتر زیر درخت با عمق بیشتر قرار می‌گیرد که فقط در صورتی که عمق‌ها برابر باشند، عمق درخت حاصل افزایش میابد. در این الگوریتم به به جای عمق از واژه مرتبه استفاده می‌شود، زیرا اگر از فشرده سازی مسیر(در ذیل توضیح داده خواهد شد) هم استفاده کنیم، دیگر مرتبه برابر با عمق درخت نخواهد بود. تعریف می‌کنیم که درخت‌های تک عضوی دارای مرتبه صفر هستند و در هر مرحله که دو درخت دارای مرتبه برابر r باشند، درخت حاصل از ادغام آن‌ها دارای مرتبه r+۱ خواهد بود. تنها پیاده کردن این تکنیک باعث می‌شود که زمان عملیات‌های جستجو، ادغام و ایجاد مجموعه به‌طور سرشکن برابر (O(log n باشد. ایده این است که هر راسی که در مسیر به راس ریشه وجود دارد، می‌تواند به صورت مستقیم به ریشه متصل شود، زیرا همه این رئوس یک نماینده مشترک دارند. | ## بخش 3: مجموعه‌های مجزا (ساختمان داده) | برای پیاده کردن این تکنیک، در هنگامی که جستجو به صورت بازگشتی از رئوس درخت به سمت ریشه حرکت می‌کند، پدر هر راس را برابر ریشه‌ای قرار می‌دهد که پیدا کرده‌است. درخت حاصل کم عمق تر از درخت اولیه‌است که باعث سریع تر شدن عملیات‌ها روی این رئوس و نوادگان آن‌ها می‌شود. چون (α(n معکوس این تابع است، (α(n برای تمامی مقادیر کاربردی n کمتر از ۵ است؛ بنابراین زمان سرشکن شده برای هر عملیات یک ثابت کوچک است. این مدل می‌تواند برای بررسی کردن این که آیا دو راس در یک مؤلفه قرار دارند یا این که آیا اضافه کردن یال بین آن‌ها می‌تواند یک دور ایجاد کند، به کار برود. این مدل در پیاده‌سازی الگوریتم کروسکال برای پیدا کردن زیر درخت فراگیر با کمترین وزن در یک گراف نیز به کار می‌رود. توجه کنید که ساختمان داده مجموعه‌های مجزا اجازه حذف یال‌ها را (حتی در صورتی که از دغام بر حسب مرتبه و فشرده سازی مسیر استفاده نکنیم) نمی‌دهد. تاریخچه با وجود اینکه ایده‌های مجموعه‌های مجزا برای مدت‌ها مورد استفاده قرار می‌گرفت، رابرت تارژان اولین کسی بود که کران بالای این مسئله که برابر معکوس تابع اکرمن می‌باشد را در سال ۱۹۷۵ به دست آورد. تا قبل از این زمان، بهترین کران برابر (O(log * n یک تابع کند دیگر (اما نه به کندی معکوس تابع اکرمن) بود. | ## جمع‌بندی | همچنین تارژان و فنلیوون یک الگوریتم یکبار اجرا را طراحی کردند که در عمل، کارا تر است اما در بدترین حالت، دو الگوریتم دارای پیچیدگی زمانی برابری هستند.