الگوریتم کمترین والدین مشترک تارجان

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم کمترین والدین مشترک تارجان در علوم کامپیوتر الگوریتم کمترین جد مشترک Tarjan (یا دقیق تر، پایین ترین جد مشترک) الگوریتمی است که بر اساس ساختمان داده‌های مجزا پایین ترین جد مشترک بین دو گره را پیدا می‌کند. پایین ترین جد مشترک دو گره d و e گره g از درخت ریشه دار T است که از بین گره‌هایی که هم جد e و هم جد d هستند بیشترین عمق را دارد. این الگوریتم به افتخار Robert Tarjan که در سال ۱۹۷۹ این تکنیک را ابداع کرد نام گذاری شده‌است.الگوریتم تارجان آفلاین است به این معنی که هنگام اجرا، تمام جفت گره ها باید قابل دسترسی باشند. ساده ترین نسخه الگوریتم از ساختمان داده های مجموعه استفاده می کند که نسبت به دیگر ساختمان داده ها کندتر است. بهینه سازی که توسط ‎Gabow & Tarjan (1983)‎ ارائه شد سرعت الگوریتم را به سرعت خطی کاهش داد.

الگوریتم[ویرایش]

شبه کد زیر پایین ترین جد مشترک هر دو جفت گره ها از مجموعه P را بدست می دهد.n.children فرزندان گره n را بدست می دهد. این الگوریتم همچنین از توابع MakeSet، Findو Union از جنگل های مجزا استفاده می کند.تابع TarjanOLCA گره ای را به عنوان ورودی دریافت و پایین ترین جد مشترک تمام جفت گره ها را در خروجی چاپ می کند.

 function TarjanOLCA(u)
     MakeSet(u);
     u.ancestor := u;
     for each v in u.children do
         TarjanOLCA(v);
         Union(u,v);
         Find(u).ancestor := u;
     u.colour := black;
     for each v such that {u,v} in P do
         if v.colour == black
             print "Tarjan's Least Common Ancestor of " + u +
                   " and " + v + " is " + Find(v).ancestor + ".";


منطق الگوریتم به این صورت است که در ابتدا تمام گره ها سفید هستند، بعد از این که آن گره و تمام فرزندانش بازدید شدند سیاه می شود. پایین ترین جد مشترک فقط و فقط پس بلافاصله پس از سیاه شدن یک گره بدست می آید.

جستارهای وابسته[ویرایش]

منابع[ویرایش]