سلام
یک سوال از ۶۰۰ مساله!
درخت بدون جهت و بدون وزن با n راس داریم ، سریع ترین الگوریتم برای یافتن قطر از چه مرتبه ای است؟ قطر یک گراف ، حداکثر طول مسیر بین دو راس در گراف است.
جواب : [tex]O(n)[/tex]
من هرچی فکر میکنم میشه [tex]O(n^{2})[/tex] اونم با DFS زدن به ازای هر راس.
با DFS و استفاده از لیست مجاورت برابر میشه با
O(E + V)
چون در درخت تعداد یالها یکی کمتر از تعداد درخت هاست، میشه
O(2V-1)=O(V)
البته این استدلال خودم بود و ممکنه اشتباه باشه
Sent from my SM-T210R using Tapatalk
خیلی راحت با زدن دو تا bfs
اولیش برای پیدا کردن عمیق ترین گره بعد از گره عمیق یک bfs دیگر لازم است برای رسیدن به عمیق ترین گره از گره عمیق!!! که برابر ۲n می شه.
(۱۲ دى ۱۳۹۲ ۰۱:۳۴ ق.ظ)keywan78 نوشته شده توسط: خیلی راحت با زدن دو تا bfsاین عمیق ترین گره اولی که میگی از کدوم گره بدست آوردید؟ اینجا ظاهرا ریشه معلوم نیست
اولیش برای پیدا کردن عمیق ترین گره بعد از گره عمیق یک bfs دیگر لازم است برای رسیدن به عمیق ترین گره از گره عمیق!!! که برابر ۲n می شه.
(۱۲ دى ۱۳۹۲ ۰۱:۳۴ ق.ظ)keywan78 نوشته شده توسط: خیلی راحت با زدن دو تا bfs
اولیش برای پیدا کردن عمیق ترین گره بعد از گره عمیق یک bfs دیگر لازم است برای رسیدن به عمیق ترین گره از گره عمیق!!! که برابر ۲n می شه.
اره! حق با شماست. در واقع چون درخت هست این کار رو میتونیم انجام بدیم. برای هر گره [tex]d(u)[/tex] ای که هر بار حساب میشه میشه عمقش ، پس همون با یه بار BFS و مقایسه [tex]d(u)[/tex] ها میشه به جواب رسید. دوبار نیاز نیست درسته؟
یک سوال دیگر!
همون سوال بالا رو میشه در دو حالت زیر بگید چی میشه
۱- اگر درخت نباشه و گراف بدون جهت ساده باشه.
۲- اگر گراف جهت دار ساده باشه.
(۱۲ دى ۱۳۹۲ ۰۸:۴۹ ق.ظ)e.sharmi نوشته شده توسط:(12 دى ۱۳۹۲ ۰۱:۳۴ ق.ظ)keywan78 نوشته شده توسط: خیلی راحت با زدن دو تا bfs
اولیش برای پیدا کردن عمیق ترین گره بعد از گره عمیق یک bfs دیگر لازم است برای رسیدن به عمیق ترین گره از گره عمیق!!! که برابر ۲n می شه.
اره! حق با شماست. در واقع چون درخت هست این کار رو میتونیم انجام بدیم. برای هر گره [tex]d(u)[/tex] ای که هر بار حساب میشه میشه عمقش ، پس همون با یه بار BFS و مقایسه [tex]d(u)[/tex] ها میشه به جواب رسید. دوبار نیاز نیست درسته؟
یک سوال دیگر!
همون سوال بالا رو میشه در دو حالت زیر بگید چی میشه
۱- اگر درخت نباشه و گراف بدون جهت ساده باشه.
۲- اگر گراف جهت دار ساده باشه.
نه با یک بار نمیشه چون مقایسه ها خودشون زمان برند nlogn و بهترین کار همون دو بار bfs هستش.
۱/برای سوال اولتون اگه یک گراف ساده باشه و مسیرمون بدون راس تکراری باشه(از تعریف قطر به دست میاد) . که با یک bfs میشه درخت گراف ساده رو کشید و قطر اون رو حساب کرد.
۲/ براس سوال ۲ باید بر روی هر راس یک dfs زد.
(۱۲ دى ۱۳۹۲ ۱۲:۳۷ ب.ظ)keywan78 نوشته شده توسط:(12 دى ۱۳۹۲ ۰۸:۴۹ ق.ظ)e.sharmi نوشته شده توسط:(12 دى ۱۳۹۲ ۰۱:۳۴ ق.ظ)keywan78 نوشته شده توسط: خیلی راحت با زدن دو تا bfs
اولیش برای پیدا کردن عمیق ترین گره بعد از گره عمیق یک bfs دیگر لازم است برای رسیدن به عمیق ترین گره از گره عمیق!!! که برابر ۲n می شه.
اره! حق با شماست. در واقع چون درخت هست این کار رو میتونیم انجام بدیم. برای هر گره [tex]d(u)[/tex] ای که هر بار حساب میشه میشه عمقش ، پس همون با یه بار BFS و مقایسه [tex]d(u)[/tex] ها میشه به جواب رسید. دوبار نیاز نیست درسته؟
یک سوال دیگر!
همون سوال بالا رو میشه در دو حالت زیر بگید چی میشه
۱- اگر درخت نباشه و گراف بدون جهت ساده باشه.
۲- اگر گراف جهت دار ساده باشه.
نه با یک بار نمیشه چون مقایسه ها خودشون زمان برند nlogn و بهترین کار همون دو بار bfs هستش.
۱/برای سوال اولتون اگه یک گراف ساده باشه و مسیرمون بدون راس تکراری باشه(از تعریف قطر به دست میاد) . که با یک bfs میشه درخت گراف ساده رو کشید و قطر اون رو حساب کرد.
۲/ براس سوال ۲ باید بر روی هر راس یک dfs زد.
آهان. ممنون. متوجه شدم