سئوالات الگوریتم رو بهتر از بقیه جواب دادم ولی درکل مفهومی بودند و با بلد بودن شکل کلی الگوریتم و ویژگی های هر الگوریتم راحت حل میشدند
الان سئوالات زیاد یادم نیست
یک سئوال در مورد پیچیدگی زمانی رو من زدم( O(V+H شما چطور زدید؟
سئوالی که در مورد الگوریتم فلوید بود رو نزدم(که میگفت اگر گرافی دارای یال منفی باشه الگوریتم وجود دور رو پیدا میکنه یا نه؟)
یکی از سئوالات هم در مورد جستجوی گراف به طوریکه دورترین گره را بتونیم حتما پیدا کنیم.من زدم پیمایش DFS همون عمقی
(الان صورت سئوال زیاد یادم نیست)
dfs که غلطه میفته توی لوپ!!! ممکنه به ح.اب نرسه
برعکس اگر BFS باشه میفته توی loop _ بقیه گزینه‌ها هم برای پیدا کردن درخت پوشای کمینه بود نه پیدا کردن دورترین گره
(۲۸ بهمن ۱۳۹۰ ۰۵:۰۷ ب.ظ)fatima1537 نوشته شده توسط: سئوالات الگوریتم رو بهتر از بقیه جواب دادم ولی درکل مفهومی بودند و با بلد بودن شکل کلی الگوریتم و ویژگی های هر الگوریتم راحت حل میشدندمن اینو زدم
الان سئوالات زیاد یادم نیست
یک سئوال در مورد پیچیدگی زمانی رو من زدم( O(V+H شما چطور زدید؟
سئوالی که در مورد الگوریتم فلوید بود رو نزدم(که میگفت اگر گرافی دارای یال منفی باشه الگوریتم وجود دور رو پیدا میکنه یا نه؟)
vlog v + e
فلوید هم میشد با یک بار اجرای مجدد دور منفی تشخیص داده میشه. من که اشتباهیزدم
اون دورترین راس میشه BFS. نزدیک‌ترین فاصله‌ی راس‌ها رو با BFS میشه پیدا کرد. در نتیجه وقتی با BFS کل گراف رو گشتیم، آخرین سطحی که بهش رسیدیم راس‌هاش بیشترین «کمترین فاصله» رو دارن نسبت به راس شروع.
۱) بلندترین فاصله: BFS
۲) کوتاهترین مسیر با یالهای مثبت: E log V
اره bfs جواب رو میده اما این سریع ترین جواب رو میخواست که bfs کندترینه
(۲۸ بهمن ۱۳۹۰ ۰۶:۱۳ ب.ظ)martianboy نوشته شده توسط: اون دورترین راس میشه BFS. نزدیک‌ترین فاصله‌ی راس‌ها رو با BFS میشه پیدا کرد. در نتیجه وقتی با BFS کل گراف رو گشتیم، آخرین سطحی که بهش رسیدیم راس‌هاش بیشترین «کمترین فاصله» رو دارن نسبت به راس شروع.
جواب این سئوال با ۲ بار dfs پیدا میشه
در clrs توضیح داده
(۲۸ بهمن ۱۳۹۰ ۰۶:۴۵ ب.ظ)k_111 نوشته شده توسط: جواب این سئوال با ۲ بار dfs پیدا میشهیعنی شما هم با من هم عقیده‌اید که جستجوی عمقی بهترینه؟ توی CLRS هم گفته؟
در clrs توضیح داده
اون سوال در مورد مرتب سازی RADIX SORT ?
A غلط
B درست
من dfs زدم .
من هر دو را زدم درست bکه مطمین بوم ولی a
d+r*s
خب حالا به جای r
log می ذاریم چون هر بار نصف میشه
سوال اول چی زدین ؟؟؟؟؟؟؟؟؟؟؟؟؟/
دوستان همه این سوال‌ها تکراری بودن، من چک کردم
سوال فلوید گزینه ۱
طولانی ترین مسیر bfs
مرتبه زمانی e log v یا v log e
(۲۸ بهمن ۱۳۹۰ ۰۵:۲۲ ب.ظ)fatima1537 نوشته شده توسط: یکی از سئوالات هم در مورد جستجوی گراف به طوریکه دورترین گره را بتونیم حتما پیدا کنیم.من زدم پیمایش DFS همون عمقی
(الان صورت سئوال زیاد یادم نیست)
درسته منم همینو زدم،چون گفته بود گراف بدون وزن BFS که نمیشد،دایکسترا م که واسه دورترین جواب نمیده،گزینه دیگشم که پرت بود.