با 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 زد.

آهان. ممنون. متوجه شدم