پایین‌ترین جد مشترک - الگوریتم آفلاین تارجان¶
درختی به نام $G$ با $n$ رأس و $m$ پرس‌وجو (query) به شکل $(u, v)$ داریم. برای هر پرس‌وجوی $(u, v)$، می‌خواهیم پایین‌ترین جد مشترک (LCA) دو رأس $u$ و $v$ را پیدا کنیم؛ یعنی رأسی که هم جد $u$ و هم جد $v$ باشد و بیشترین عمق را در درخت داشته باشد. هر رأس جد خودش نیز محسوب می‌شود، بنابراین LCA می‌تواند یکی از خود دو رأس باشد.
در این مقاله، مسئله را به صورت آفلاین حل می‌کنیم؛ یعنی فرض می‌کنیم تمام پرس‌وجوها از قبل مشخص هستند و بنابراین می‌توانیم به آن‌ها با هر ترتیبی که بخواهیم پاسخ دهیم. الگوریتم زیر به ما اجازه می‌دهد تا به تمام $m$ پرس‌وجو در زمان کلی $O(n + m)$ پاسخ دهیم، یعنی برای مقادیر به اندازه‌ی کافی بزرگ $m$، زمان پاسخ به هر پرس‌وجو $O(1)$ خواهد بود.
الگوریتم¶
این الگوریتم به نام رابرت تارجان نام‌گذاری شده است که آن را در سال ۱۹۷۹ کشف کرد و همچنین کمک‌های شایان دیگری به ساختار داده‌ی اجتماع مجموعه‌های مجزا (Disjoint Set Union) کرده است که در این الگوریتم به طور گسترده استفاده می‌شود.
این الگوریتم با یک پیمایش DFS روی درخت به تمام پرس‌وجوها پاسخ می‌دهد. به طور مشخص، یک پرس‌وجوی $(u, v)$ در رأس $u$ پاسخ داده می‌شود، اگر رأس $v$ قبلاً پیمایش شده باشد، یا برعکس.
پس فرض کنیم در حال حاضر در رأس $v$ هستیم، فراخوانی‌های بازگشتی DFS را انجام داده‌ایم و همچنین رأس دیگر پرس‌وجوی $(u, v)$ یعنی $u$ را نیز پیمایش کرده‌ایم. بیایید ببینیم چگونه LCA این دو رأس را پیدا کنیم.
توجه داشته باشید که $\text{LCA}(u, v)$ یا خود رأس $v$ است یا یکی از اجداد آن. بنابراین باید پایین‌ترین رأس در میان اجداد $v$ (شامل خود $v$) را پیدا کنیم که رأس $u$ از نوادگان آن باشد. همچنین توجه کنید که برای یک $v$ ثابت، رأس‌های پیمایش‌شده‌ی درخت به مجموعه‌ای از مجموعه‌های مجزا تقسیم می‌شوند. هر جد $p$ از رأس $v$، مجموعه‌ی مخصوص به خود را دارد. این مجموعه شامل خود رأس $p$ و تمام زیردرخت‌هایی است که ریشه‌شان فرزندان $p$ بوده و در مسیر بین $v$ و ریشه‌ی اصلی درخت قرار ندارند. مجموعه‌ای که رأس $u$ در آن قرار دارد، $\text{LCA}(u, v)$ را مشخص می‌کند: LCA همان نماینده‌ی آن مجموعه است، یعنی رأسی که روی مسیر بین $v$ و ریشه‌ی درخت قرار دارد.
کافی است یاد بگیریم چگونه تمام این مجموعه‌ها را به صورت بهینه نگهداری کنیم.
برای این منظور، از ساختار داده‌ی DSU استفاده می‌کنیم.
برای اینکه بتوانیم از Union by rank استفاده کنیم، نماینده‌ی واقعی هر مجموعه (یعنی رأسی که در مسیر بین $v$ و ریشه درخت قرار دارد) را در آرایه‌ی ancestor ذخیره می‌کنیم.
بیایید پیاده‌سازی DFS را بررسی کنیم.
فرض کنید در حال پیمایش رأس $v$ هستیم.
این رأس را در یک مجموعه‌ی جدید در DSU قرار می‌دهیم، ancestor[v] = v.
طبق معمول، تمام فرزندان $v$ را پردازش می‌کنیم.
برای این کار، ابتدا به صورت بازگشتی DFS را از آن فرزند فراخوانی می‌کنیم و سپس آن فرزند را به همراه تمام زیردرختش به مجموعه‌ی $v$ اضافه می‌کنیم.
این کار را می‌توان با تابع union_sets و انتساب زیر انجام داد: ancestor[find_set(v)] = v (این کار ضروری است، زیرا union_sets ممکن است نماینده‌ی مجموعه را تغییر دهد).
در نهایت، پس از پردازش تمام فرزندان، می‌توانیم به تمام پرس‌وجوهای به شکل $(u, v)$ که در آن‌ها $u$ قبلاً پیمایش شده است، پاسخ دهیم.
پاسخ پرس‌وجو، یعنی LCA دو رأس $u$ و $v$، برابر با رأس ancestor[find_set(u)] خواهد بود.
به راحتی می‌توان دید که هر پرس‌وجو تنها یک بار پاسخ داده می‌شود.
بیایید پیچیدگی زمانی این الگوریتم را مشخص کنیم.
اولاً، به دلیل وجود DFS، پیچیدگی زمانی $O(n)$ داریم.
دوماً، فراخوانی‌های تابع union_sets را داریم که $n$ بار اتفاق می‌افتند و در نتیجه $O(n)$ زمان می‌برند.
و سوماً، فراخوانی‌های تابع find_set برای هر پرس‌وجو را داریم که پیچیدگی $O(m)$ را نتیجه می‌دهد.
بنابراین، در مجموع پیچیدگی زمانی برابر با $O(n + m)$ است، که به این معناست که برای مقادیر به اندازه‌ی کافی بزرگ $m$، این پیچیدگی معادل $O(1)$ برای پاسخ به هر پرس‌وجو است.
پیاده‌سازی¶
در ادامه پیاده‌سازی این الگوریتم آمده است. پیاده‌سازی DSU در اینجا آورده نشده است، زیرا می‌توان از آن بدون هیچ تغییری استفاده کرد.
vector<vector<int>> adj;
vector<vector<int>> queries;
vector<int> ancestor;
vector<bool> visited;
void dfs(int v)
{
visited[v] = true;
ancestor[v] = v;
for (int u : adj[v]) {
if (!visited[u]) {
dfs(u);
union_sets(v, u);
ancestor[find_set(v)] = v;
}
}
for (int other_node : queries[v]) {
if (visited[other_node])
cout << "LCA رئوس " << v << " و " << other_node
<< " برابر است با " << ancestor[find_set(other_node)] << ".\n";
}
}
void compute_LCAs() {
// مقداردهی اولیه n، adj و DSU
// for (each query (u, v)) {
// queries[u].push_back(v);
// queries[v].push_back(u);
// }
ancestor.resize(n);
visited.assign(n, false);
dfs(0);
}