سلام
محاسبه قطر گراف(ماکزیمم کوتاه ترین مسیرهایربین گره ها)رو چجوری با bfsمیشه بدست اوورد؟
دکتر یوسفی گفتن bfsرو هر گره حساب میکنیم.کسی میدونه چجوریه با مثال بگه؟
برا درخت ی بار bfs کافیه بزنید چون دوری وجود نداره بلندترین مسیر میشه قطر
O(v
برا گراف باید به ازای هر گره بزنید چون دور داریم و بلندترین و انتخاب کنیم o (v*v
قطر بلند ترین مگه نیست؟
فکر کنم با الگوریتم DFS برای گراف بدون وزن البته یا وزن برابر به جواب
میشه رسید
مرتبش هم n
(۱۰ بهمن ۱۳۹۳ ۰۶:۵۷ ب.ظ)IT93 نوشته شده توسط: برا درخت ی بار bfs کافیه بزنید چون دوری وجود نداره بلندترین مسیر میشه قطرسلام
O(v
برا گراف باید به ازای هر گره بزنید چون دور داریم و بلندترین و انتخاب کنیم o (v*v
ایشون تو جزوشون نوشته برای هر راس bfsمیزنیم مرتبه رو (لیست مجاورتی گرفتن)
O(v(v+e))
تا اینجاشو میدونم ،تو مثال ک میخام بزنم نمیفهمم چجور قطر گراف رو از رو bfsمیفهمه
(۱۰ بهمن ۱۳۹۳ ۰۷:۰۸ ب.ظ)tm.viper نوشته شده توسط: قطر بلند ترین مگه نیست؟قطر گراف بزرگترین کوتاه تریم مسیر بین گره ها...کوتاه ترین مسیر از روbfsبدست میاد دیگه!
فکر کنم با الگوریتم DFS برای گراف بدون وزن البته یا وزن برابر به جواب
میشه رسید
مرتبش هم n
آخه در مورد درخت یه سوال امروز تو مدرسان اومد
گفتم شاید واسه گراف هم dfs باشه
(۱۰ بهمن ۱۳۹۳ ۰۸:۱۹ ب.ظ)tm.viper نوشته شده توسط: آخه در مورد درخت یه سوال امروز تو مدرسان اومد
گفتم شاید واسه گراف هم dfs باشه
راجبش اینکه میشه یا نه باید فک کنم اما با dfs هم اگر بشه باز هزینه ش تویه گراف میشه مثل bfsیعنی خلاصه n نمیشه
(۱۰ بهمن ۱۳۹۳ ۰۷:۳۵ ب.ظ)shamim_70 نوشته شده توسط: قطر گراف بزرگترین کوتاه تریم مسیر بین گره ها...کوتاه ترین مسیر از روbfsبدست میاد دیگه!
همون bfs هست دیگه ! چیز خاصی نداره ک !bfs بزنید به ازای هر راس .ینی مبدا باید ب ازی همه راس ها قرار بگیره یا بعبارت دیگه هر راس حتما یکبار مبدا قرار گیرد!همه طول مسیر ها رو بنوسید در نهایت بزرگترین رو اانتخاب کنید