2359. نزدیکترین گره را به دو گره داده شده پیدا کنید

2359. نزدیکترین گره را به دو گره داده شده پیدا کنید

مشکل: واسطه

مباحث: Depth-First Searchبا Graph

به شما داده می شود متمایل نمودار نمودار از n گره های شماره از 0 به n - 1، جایی که هر گره در آن وجود دارد بیشتر یکی لبه خروجی

نمودار با یک داده نشان داده شده است 0-شاخص مجموعه edges از اندازه n، نشان می دهد که یک لبه کارگردانی از گره وجود دارد i گره زدن edges[i]بشر در صورت وجود لبه خروجی از i، پس edges[i] == -1بشر

به شما دو عدد صحیح نیز داده می شود node1 وت node2بشر

بازگشت در فهرست از گره ای که از هر دو قابل دستیابی است node1 وت node2، به گونه ای که حداکثر بین فاصله از node1 به آن گره ، و از node2 به آن گره است به حداقل رساندنبشر اگر چندین پاسخ وجود دارد ، گره را با کوچکترین فهرست ، و در صورت وجود پاسخ احتمالی ، بازگشت -1بشر

توجه داشته باشید که edges ممکن است حاوی چرخه باشد.

مثال 1:

• ورودی: لبه ها = [2,2,3,-1]، node1 = 0 ، node2 = 1
• خروجی: 2
• توضیح: فاصله از گره 0 تا گره 2 1 و فاصله از گره 1 تا گره 2 1 است.
  • حداکثر این دو مسافت 1 است. می توان ثابت کرد که ما نمی توانیم گره ای با حداکثر فاصله کوچکتر از 1 بدست آوریم ، بنابراین گره 2 را برمی گردانیم.

مثال 2:

• ورودی: لبه ها = [1,2,-1]، node1 = 0 ، node2 = 2
• خروجی: 2
• توضیح: فاصله از گره 0 تا گره 2 2 است و فاصله از گره 2 تا خود 0 است.
  • حداکثر این دو مسافت 2 است. می توان ثابت کرد که ما نمی توانیم گره ای با حداکثر فاصله کوچکتر از 2 بدست آوریم ، بنابراین گره 2 را برمی گردانیم.

محدودیت ها:

• n == edges.length
• 2 <= n <= 105
• -1 <= edges[i] < n
• edges[i] != i
• 0 <= node1, node2 < n

نکته:

1. چگونه می توانید کوتاهترین فاصله را از یک گره به تمام گره های موجود در نمودار پیدا کنید؟
2. برای یافتن کوتاهترین فاصله از Node1 و Node2 به همه گره های موجود در نمودار ، از BFS استفاده کنید. سپس بیش از همه گره ها تکرار کنید و گره را با حداقل فاصله حداکثر پیدا کنید.

راه حل:

ما باید نزدیکترین گره را در یک نمودار کارگردانی پیدا کنیم که از دو گره داده شده قابل دسترسی باشد ، node1 وت node2، به گونه ای که حداکثر فاصله از node1 وت node2 به این گره به حداقل می رسد. اگر چندین گره این شرایط را برآورده کند ، ما کوچکترین شاخص را در بین آنها برمی گردانیم. اگر چنین گره ای وجود نداشته باشد ، ما برمی گردیم -1بشر

رویکرد

1. تجزیه و تحلیل مسئله: نمودار به عنوان یک نمودار کارگردانی که در آن هر گره حداکثر یک لبه خروجی دارد ، نشان داده شده است. این ساختار مسیر را ساده می کند زیرا هر گره به یک مسیر منحصر به فرد (یا یک چرخه) منتهی می شود. هدف این است که یک گره مشترک را از هر دو پیدا کنید node1 وت node2 این حداکثر فاصله آنها را به این گره به حداقل می رساند.
2. شهود: برای هر گره ، ما به کوتاهترین مسافت ها نیاز داریم node1 وت node2بشر با توجه به ماهیت قطعی نمودار (هر گره حداکثر یک لبه خروجی دارد) ، می توانیم نمودار را از هر گره شروع کنیم تا مسافت ها را به همه گره های قابل دسترسی ضبط کنیم. این از الگوریتم های پیچیده مسیر کوتاه مانند BFS برای نمودارهای عمومی جلوگیری می کند.
3. انتخاب الگوریتم:
   • محاسبه فاصله: برای هر گره شروع (node1 وت node2) ، هنگام ضبط فاصله از هر گره بازدید شده ، نمودار را طی کنید. هنگام مواجهه با گره ای که قبلاً بازدید شده است (نشانگر یک چرخه) یا یک گره با لبه خروجی متوقف شوید.
   • پیدا کردن گره بهینه: از طریق همه گره ها تکرار کنید. برای گره های قابل دسترسی از هر دو node1 وت node2، حداکثر مسافت خود را محاسبه کنید. گره را با کوچکترین مسافت حداکثر ردیابی کنید. اگر چند گره حداکثر فاصله یکسان دارند ، کوچکترین شاخص را انتخاب کنید.
4. تجزیه و تحلیل پیچیدگی:
   • پیچیدگی زمانی: o (n) ، جایی که n تعداد گره ها است. هر گذرگاه هر گره را حداکثر یک بار پردازش می کند و تکرار نهایی خطی است.
   • پیچیدگی فضا: o (n) برای ذخیره مسافت از node1 وت node2بشر

بیایید این راه حل را در PHP پیاده سازی کنیم: 2359. نزدیکترین گره را به دو گره داده شده پیدا کنید

/**
 * @param Integer[] $edges
 * @param Integer $node1
 * @param Integer $node2
 * @return Integer
 */
function closestMeetingNode($edges, $node1, $node2) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example 1
$edges = [2, 2, 3, -1];
$node1 = 0;
$node2 = 1;
echo closestMeetingNode($edges, $node1, $node2) . "\n"; // Output: 2

// Example 2
$edges = [1, 2, -1];
$node1 = 0;
$node2 = 2;
echo closestMeetingNode($edges, $node1, $node2) . "\n"; // Output: 2
?>

توضیح:

1. شروع: دو آرایه از راه دور ، dist1 وت dist2، اولیه به -1 (نشانگر گره های غیرقابل دستیابی) برای همه گره ها.
2. عبور از node1: شروع در node1، نمودار را طی کنید و فاصله هر گره ای را که با آن روبرو شده است ، ضبط کنید. اگر یک گره مجدداً مورد بررسی قرار گرفت (چرخه شناسایی شده) یا هیچ لبه خروجی وجود ندارد.
3. عبور از node2: همان فرآیند را که از آن شروع می شود تکرار کنید node2بشر
4. یافتن گره بهینه: برای هر گره ، اگر از هر دو قابل دسترسی باشد node1 وت node2، حداکثر دو فاصله را محاسبه کنید. گره را با کوچکترین مسافت حداکثر ردیابی کنید. اگر چند گره حداکثر به حداقل برسد ، کوچکترین شاخص انتخاب می شود.
5. نتیجه: گره بهینه را برگردانید یا -1 اگر هیچ گره قابل دسترسی مشترک وجود نداشته باشد.

این رویکرد به طور مؤثر از ساختار قطعی نمودار برای محاسبه مسافت ها و یافتن گره جلسه بهینه با حداقل سربار محاسباتی استفاده می کند.

پیوندهای تماس

اگر این سریال را مفید دیدید ، لطفاً در نظر بگیرید مخزن یک ستاره در GitHub یا به اشتراک گذاری پست در شبکه های اجتماعی مورد علاقه خود. حمایت شما برای من بسیار معنی دارد!

اگر می خواهید مطالب مفید تری مانند این ، احساس راحتی کنید که از من پیروی کنید: