کلاس‌های هم‌ارزی
از فهرستی از جفت‌های i ≡ j، کلاس‌های هم‌ارزی را پیدا می‌کند: هر جفت را در لیست هر دو عضو می‌گذارد و بعد با یک پشته همه‌ی اعضای یک کلاس را جمع می‌کند؛ O(n + m).
یک رابطه‌ی هم‌ارزی بازتابی، تقارنی و ترایا است، پس از چند جفت i ≡ j می‌شود همه‌ی اعضای هم‌ارز را نتیجه گرفت. الگوریتم هوروویتز دو مرحله دارد:
- زمان:
O(n + m) - حافظه:
O(n + m) - هوروویتز–ساهنی، فصل ۴
۱۲ شیء و ۹ جفت؛ سه کلاس به دست می‌آید: {۰، ۴، ۱۱، ۲، ۷}، {۱، ۳، ۵} و {۶، ۱۰، ۸، ۹}.
def equivalence(pairs):# Objects are 0..n-1; each row of pairs says i ≡ j.n = 0for i, j in pairs:n = max(n, i + 1, j + 1)seq = [[] for _ in range(n)]rows = [[x, seq[x], "·"] for x in range(n)] # for the picture: object, partners, classfor i, j in pairs:seq[i].append(j)seq[j].append(i)out = [False] * nclasses = []for i in range(n):if out[i]:continueout[i] = Truecls = [i]rows[i][2] = len(classes)stack = [i]while stack:x = stack.pop()for y in seq[x]:if not out[y]:out[y] = Truecls.append(y)rows[y][2] = len(classes)stack.append(y)classes.append(cls)return classes
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
pairs list
Call stack
- equivalence()خط 1
توضیح
ایده
یک رابطه‌ی هم‌ارزی بازتابی، تقارنی و ترایا است، پس از چند جفت i ≡ j می‌شود همه‌ی اعضای هم‌ارز را نتیجه گرفت. الگوریتم هوروویتز دو مرحله دارد:
- خواندن جفت‌ها: برای هر جفت،
jرا در لیستiوiرا در لیستjمی‌گذارد (تقارن). - ساختن کلاس‌ها: از اولین شیئی که هنوز در کلاسی نیست شروع می‌کند، آن را در پشته می‌گذارد، و هر بار یک عضو را برمی‌دارد و همه‌ی شریک‌های تازه‌اش را به کلاس اضافه و در پشته می‌گذارد (ترایایی).
این همان پیدا کردن مؤلفه‌های همبند یک گراف با DFS است.
هزینه
با n شیء و m جفت، هر جفت دو بار در لیست‌ها می‌آید و هر کدام یک بار بررسی می‌شود: O(n + m).
ورودی
هر سطر یک جفت [i, j] است. تعداد شیءها از بزرگ‌ترین عدد به دست می‌آید.