پایین‌ترین جد مشترک

در این درخت پایین ترین جد مشترک از گره های x و y با رنگ سبز تیره مشخص شده است . اجداد مشترک دیگر با سبز کم رنگ نشان داده شده است .

در نظریه گراف و علوم کامپیوتر‍‍ پایین‌ترین جد مشترک (LCA) دو گره v و w در یک درخت پایین‌ترین (یعنی عمیق ترین) گره است که هر دو v و w به عنوان فرزندان آن گره باشند . LCA دو راس v و w در درخت T جد مشترکی از v و w که در فاصله دورتری از ریشه واقع شده‌است . محاسبه پایین‌ترین جد مشترک ممکن است مفید باشد به عنوان مثال به عنوان بخشی از یک روش برای تعیین فاصله بین جفت از گره‌ها در یک درخت: فاصله از v به w را می‌توان جمع فاصله از ریشه به v و فاصله از ریشه به w منهای دو برابر فاصله از ریشه به پایین‌ترین جد مشترک (Djidjev, Pantziou & Zaroliagis 1991) در نظر گرفت . در هستی شناسی, پایین‌ترین جد مشترک به عنوان least common subsumer نیز مشهور است .

الگوریتم

فرض کنید میخواهیم پایین‌ترین جد مشترک دو راس v و w را پیدا کنیم . ابتدا با استفاده از الگوریتم جستجوی عمق اول پدر گره v را در $father[v]$ ذخیره می کنیم . این الگوریتم از $O(n)$ است .

ساده‌ترین راه این است که ابتدا دو گره را هم ارتفاع کنیم سپس تا زمانی که دو گره برابر نشدند هر دو را بالا بیاوریم از آن رو که ریشه جد مشترک آن هاست ، این فرایند پایان پذیر است و گره ای که در آن متوقف می شویم همان پایین‌ترین جد مشترک است . این الگوریتم با فرض داشتن پدر هر گره به عنوان پیش پردازش ، هر درخواست را در $O(n)$ جواب می‌دهد .

راه بهتر استفاده از برنامه ریزی پویا است .

$ancestor[v][i]$ را $2^{i}$ گره بالای گره v در نظر می گیریم .

• به ازای هر v و i = 0 مقدار $ancestor[v][i]=father[v]$ است .
• به ازای $i>0$ مقدار $ancestor[v][i]=ancestor[ancestor[v][i-1]][i-1]$ است .

این کار به عنوان پیش پردازش برای پاسخ دادن به درخواست هاست و از $O(n*log(n))$ است .

حال می خواهیم پایین‌ترین جد مشترک w و v را بیابیم .

ابتدا گره ای که در ارتفاع بیشتری قرار دارد با $O(log(n))$ با دیگری هم ارتفاع می کنیم .

حال فرض می کنیم فاصله این دو گره از پایین‌ترین جد مشترکشان ، حداکثر k بیتی است .

از پر ارزش‌ترین بیت شروع می کنیم و مقدار بیت‌ها را تعیین می کنیم .

فرض کنید روی بیت i ام هستیم :

اگر $2^{i}$ امین گره بالای v و w یکسان بود این بیت ۰ و در غیر این صورت این بیت ۱ است و هر دو گره به $2^{i}$ گره بالاتر منتقل می‌شوند .

در انتها پدر هر یک از دو گره ، پایین‌ترین جد مشترک v و w اولیه است .

این الگوریتم از $O(log(n))$ است .

کاربرد ها

این مسئله در یافتن پایین‌ترین جد مشترک کلاسها در وراثت (برنامه‌نویسی شیءگرا) و سامانه پیچیده کاربرد دارد .

منابع

• ویکی‌پدیای انگلیسی
• | المپدیا