الگوریتم کمترین والدین مشترک تارجان
From Wikipedia, the free encyclopedia
الگوریتم کمترین والدین مشترک تارجان در علوم کامپیوتر الگوریتم کمترین جد مشترک Tarjan (یا دقیق تر، پایینترین جد مشترک) الگوریتمی است که بر اساس ساختمان دادههای مجزا پایینترین جد مشترک بین دو گره را پیدا میکند. پایینترین جد مشترک دو گره d و e گره g از درخت ریشه دار T است که از بین گرههایی که هم جد e و هم جد d هستند بیشترین عمق را دارد. این الگوریتم به افتخار Robert Tarjan که در سال ۱۹۷۹ این تکنیک را ابداع کرد نام گذاری شدهاست.الگوریتم تارجان آفلاین است به این معنی که هنگام اجرا، تمام جفت گرهها باید قابل دسترسی باشند. سادهترین نسخه الگوریتم از ساختمان دادههای مجموعه استفاده میکند که نسبت به دیگر ساختمان داده ها کندتر است. بهینه سازی که توسط (Gabow و Tarjan 1983) ارائه شد سرعت الگوریتم را به سرعت خطی کاهش داد.
این مقاله نیازمند ویکیسازی است. لطفاً با توجه به راهنمای ویرایش و شیوهنامه، محتوای آن را بهبود بخشید. |