اتصال چند درخت تو یه گراف

[root88]

با سلام
من یه گراف دارم شامل تعدادی درخت می خوام با کمترین هزینه و از طریق نودهای میانی این درخت ها را به هم کانکت کنم(فقط درخت ها لازمه نه متصل کردن کل گراف) . دوستان در این زمینه لطفا منو راهنمایی کنید. ممنون میشم.

[qwerty11]

از هر درخت یه راس رو انتخاب کن و به بقیه ی رئوسی که انتخاب کردی وصل کن دیگه :-/

[root88]

بله ممنون، اما من یه ماتریس مجاورت از گراف دارم و یه ماتریس دیگه که هر کدوم از سطرهاش نودهای یه درخت رو نشون میده. می خوام مثلا فاصله نود قرمز رو از دو تا درخت شکل زیر به دست بیارم اما نمی دونم چطوری؟ البته الزاما نود قرمز مجاور نودی از درخت نیست

[qwerty11]

خوب جستجوی اول سطح این کار رو برات انجام میده دیگه.

از راس قرمز شروع میکنی و به راس های مجاورش میری و اونا رو به صف اضافه میکنی. اگر یکی از این راس ها عضو یه درخت بودن اونوقت فاصله از اون درخت به دست اومده. ...

معلومه همه چی !؟

[root88]

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

[qwerty11]

چون یال ها وزن ندارن جستجوی اول سطح جواب درست رو بهت میده.