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

در نظریه گراف و علوم کامپیوتر‍‍ پایین ترین جد مشترک ( 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 را در f a t h e r ذخیره می کنیم . این الگوریتم از O ( n ) است .
ساده ترین راه این است که ابتدا دو گره را هم ارتفاع کنیم سپس تا زمانی که دو گره برابر نشدند هر دو را بالا بیاوریم از آن رو که ریشه جد مشترک آن هاست ، این فرایند پایان پذیر است و گره ای که در آن متوقف می شویم همان پایین ترین جد مشترک است . این الگوریتم با فرض داشتن پدر هر گره به عنوان پیش پردازش ، هر درخواست را در O ( n ) جواب می دهد .
راه بهتر استفاده از برنامه ریزی پویا است .
a n c e s t o r را 2 i گره بالای گره v در نظر می گیریم . به ازای هر v و i = 0 مقدار a n c e s t o r = f a t h e r است . به ازای i > 0 مقدار a n c e s t o r = a n c e s t o r ] است . این کار به عنوان پیش پردازش برای پاسخ دادن به درخواست هاست و از O ( n ∗ l o g ( n ) ) است . حال می خواهیم پایین ترین جد مشترک w و v را بیابیم .
ابتدا گره ای که در ارتفاع بیشتری قرار دارد با O ( l o g ( n ) ) با دیگری هم ارتفاع می کنیم .
حال فرض می کنیم فاصله این دو گره از پایین ترین جد مشترکشان ، حداکثر k بیتی است .
از پر ارزش ترین بیت شروع می کنیم و مقدار بیت ها را تعیین می کنیم .
فرض کنید روی بیت i ام هستیم  :
اگر 2 i امین گره بالای v و w یکسان بود این بیت ۰ و در غیر این صورت این بیت ۱ است و هر دو گره به 2 i گره بالاتر منتقل می شوند .
در انتها پدر هر یک از دو گره ، پایین ترین جد مشترک v و w اولیه است .