چند تا سوال از مباحث گراف دارم لطفا اگه کسی میدونه جواب بده
۱) واسه پیدا کردن همه ی دورها در گراف ( جهت دار و غیر جهت دار ) باید چکار کنیم؟ با n بار dfs میشه بدست آورد. اما دلیلشو نمیفهمم
۲) پیدا کردن تمام مسیرها در بین زوج رئوس: با bfs میشه این کار رو کرد اما مرتبه ی زمانیش رو نمیدونم. الگوریتم جانسون هست اما اون واسه پیدا کردن کوتاهترین مسیر بین زوج رئوس هست! آیا واسه تمام مسیرها صدق میکنه؟
۳) در چه صورت یک گراف فقط یک ترتیب مرتب سازی توپولوژیک دارد ؟
فعلا همین ها رو جواب بدید مابقیش رو بعدا...
۲-
الگوریتم جانسون از دایجکسترا و بلمن فورد به عنوان زیر روال استفاده می کنه و کوتاه ترین مسیر بین دو گره را به شما می ده
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
اگر Bfs رو برای پیدا کزدن کوتاه ترین مسیر در یک گراف جهت دار برای هر گره اجرا کنی زمان نمایی ([tex]O(V^V)[/tex]) داری اگر روال اش رو بدون هیج تغییری اجرا کنی .برای بهبود این زمان می تونی در روالش در حین اجرا حلقه اصلی عمل Relaxtion رو انجام بدی تا کوتاه ترین انتخاب بشه یا هر مورد دیگر.
۳-
گراف باید فاقد دور و جهت دار باشه بعد اینکه زمانی یک ترتیب منحصر به فرد بعد از اجرای Topological Sort دارید که گراف همبند باشه و مولفه ناهمبند نداشته باشید اگر راس هایی داشته باشید که همبند ضعیف باشد موقع محاسبه finishing Time آنها باید مشخص کنید که کدام راس اولویت داره برای محاسبتون وگرنه یک ترتیب ندارید.