۰
subtitle
ارسال: #۱
یافتن مولفه های همبند گراف جهتدار ، باچه روش و چه مرتبه ای؟
یافتن مولفه های همبند گراف جهتدار به چه روش و با چه مرتبه ای حل میشه؟
(۱۰ بهمن ۱۳۸۹ ۱۱:۵۸ ب.ظ)arshad90 نوشته شده توسط: برای یافتن مولفه های متصل قوی در یک گراف جهتدار:
۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).
۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.
۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی fها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
![]() |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۵,۹۱۲ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۶۹۹ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
مرتبه شبه کد | rad.bahar | ۱ | ۲,۶۱۰ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۴,۷۱۶ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
مرتبه زمانی | Sanazzz | ۱۷ | ۲۳,۵۳۶ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
رنگ کردن رئوس گراف( ارشد علوم کامپیوتر ۹۸ ) | ss311 | ۰ | ۲,۳۳۷ |
۰۳ اسفند ۱۳۹۸ ۱۲:۴۳ ب.ظ آخرین ارسال: ss311 |
|
تعداد روش های نوشتن عدد n | ss311 | ۲ | ۳,۷۳۱ |
۱۳ بهمن ۱۳۹۸ ۰۵:۲۷ ب.ظ آخرین ارسال: ss311 |
|
تعداد مسیرها در گراف | ss311 | ۰ | ۲,۲۱۱ |
۰۸ بهمن ۱۳۹۸ ۱۲:۴۷ ب.ظ آخرین ارسال: ss311 |
|
مشاوره روش تحقیق و تحلیل آماری | sirvan.t | ۰ | ۲,۳۹۷ |
۱۷ آذر ۱۳۹۸ ۱۲:۵۹ ق.ظ آخرین ارسال: sirvan.t |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۴,۱۶۶ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |