مجموعه‌های مجزا (Union-Find)

بازگشتی

یال‌ها را یکی‌یکی می‌خواند و مجموعه‌ی دو سرشان را یکی می‌کند؛ با «ادغام بر اساس رتبه» و «فشرده‌سازی مسیر» هر عمل تقریباً O(1) است.

ساختار مجموعه‌های مجزا دو عمل دارد: FIND(x) (نماینده‌ی مجموعه‌ی x) و UNION(x, y) (یکی کردن دو مجموعه). هر مجموعه یک درخت است و ریشه‌اش نماینده است؛ parent[x] به پدر x اشاره می‌کند.

ادامه‌ی توضیح ↓

زمان: O(E · α(V))
حافظه: O(V)
CLRS، بخش ۱۹.۳
هوروویتز–ساهنی، فصل ۵

ورودی:

V=8 · E=7 · src=Aخروجی PDF

هشت گره؛ ادغام‌ها دو درخت با عمق ۲ می‌سازند. برای یال آخر، D — H، دو FIND از دو پله پایین‌تر شروع می‌شوند و فشرده‌سازی مسیر D و H را مستقیم به ریشه‌هایشان وصل می‌کند.

def union_find(graph, src):
parent = {v: v for v in graph}
rank = {v: 0 for v in graph}
for u in graph:
for v, _ in graph[u]:
if u > v:
continue # each undirected edge once
ru = find(parent, u)
rv = find(parent, v)
if ru == rv:
continue
if rank[ru] < rank[rv]:
ru, rv = rv, ru
parent[rv] = ru
if rank[ru] == rank[rv]:
rank[ru] = rank[ru] + 1
return parent
def find(parent, x):
if parent[x] == x:
return x
root = find(parent, parent[x])
parent[x] = root
return root

ناوردا: هر مجموعه یک درخت است که ریشه‌اش نماینده‌ی آن است؛ دو گره در یک مجموعه‌اند اگر و فقط اگر FIND هر دو یک ریشه بدهد.

شروع اجرا

گره‌ی جاری (x)
درخت کوتاه‌ترین مسیر تا اینجا
یالِ در حال بررسی

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

متغیرهای محلی

src'A'

نارنجی = در همین گام عوض شد

graph dict

'A': [('B', 1)]
'C': [('D', 1)]
'E': [('F', 1)]
'G': [('H', 1)]
'B': [('A', 1), ('D', 1)]
'F': [('E', 1), ('H', 1)]
'D': [('C', 1), ('B', 1), ('H', 1)]
'H': [('G', 1), ('F', 1), ('D', 1)]

Call stack

union_find()خط 1

گام ۱ از ۱۸۷

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

is_root
compress
ورودی فعلی (n=8)

نمایش به شکل جدول

n	is_root	compress
4	15	4.6
8	44.6	17
12	67	25.4
16	91.4	35.4
20	118.6	47.8
24	121.4	47
28	158	63.6

توضیح

ایده

دو ترفند

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

با هر دو، هر عمل به‌طور میانگین O(α(n)) است؛ α تابع معکوس آکرمان است که در عمل از ۵ بیشتر نمی‌شود.

کاربرد

مؤلفه‌های همبند، تشخیص دور و الگوریتم کروسکال (که اینجا بدون این دو ترفند پیاده شده).

در trace به چه چیزی نگاه کنی

برچسب کنار هر گره parent آن است؛ ریشه‌ها به خودشان اشاره می‌کنند.
در ورودی «مثال به سبک کتاب»، یال آخر را ببین: FIND مسیر را کوتاه می‌کند.