PDA

View Full Version : سوال: اتصال چند درخت تو یه گراف



root88
یک شنبه 24 مرداد 1389, 18:13 عصر
با سلام
من یه گراف دارم شامل تعدادی درخت می خوام با کمترین هزینه و از طریق نودهای میانی این درخت ها را به هم کانکت کنم(فقط درخت ها لازمه نه متصل کردن کل گراف) . دوستان در این زمینه لطفا منو راهنمایی کنید. ممنون میشم.

qwerty11
یک شنبه 24 مرداد 1389, 20:29 عصر
از هر درخت یه راس رو انتخاب کن و به بقیه ی رئوسی که انتخاب کردی وصل کن دیگه :-/

root88
دوشنبه 25 مرداد 1389, 23:34 عصر
بله ممنون، اما من یه ماتریس مجاورت از گراف دارم و یه ماتریس دیگه که هر کدوم از سطرهاش نودهای یه درخت رو نشون میده. می خوام مثلا فاصله نود قرمز رو از دو تا درخت شکل زیر به دست بیارم اما نمی دونم چطوری؟ البته الزاما نود قرمز مجاور نودی از درخت نیست
http://www.irupload.ir/images/1q40nhm6vwy1bbd49at.jpg

qwerty11
سه شنبه 26 مرداد 1389, 00:36 صبح
خوب جستجوی اول سطح این کار رو برات انجام میده دیگه.

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

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

root88
سه شنبه 26 مرداد 1389, 09:01 صبح
جستجوی اول سطح یا الگوریتم فلوید،اگه بخوام کوتاهترین مسیر رو به دست بیارم

qwerty11
چهارشنبه 27 مرداد 1389, 13:19 عصر
چون یال ها وزن ندارن جستجوی اول سطح جواب درست رو بهت میده.