۰
subtitle
ارسال: #۱
  
یافتن مولفه های همبند گراف جهتدار ، باچه روش و چه مرتبه ای؟
یافتن مولفه های همبند گراف جهتدار به چه روش و با چه مرتبه ای حل میشه؟
۳
ارسال: #۲
  
RE: مولفه همبند
برای یافتن مولفه های متصل قوی در یک گراف جهتدار:
۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).
۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.
۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی fها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.
۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).
۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.
۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی fها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.
ارسال: #۳
  
RE: مولفه همبند
(۱۰ بهمن ۱۳۸۹ ۱۱:۵۸ ب.ظ)arshad90 نوشته شده توسط: برای یافتن مولفه های متصل قوی در یک گراف جهتدار:
۱- DFS را روی گراف اجرا کرده و برای هر نود مقدار d/f را قرار می دهیم. (d: زمان شروع ملاقات نود در پیمایش و f: زمان پایان ملاقات نود).
۲- جهت یالها را در گراف مذکور برعکس می کنیم. یعنی اگر از a به b یک یال جهتدار داریم جهت این یال را از b به a تغییر می دهیم.
۳- مرحله آخر اینکه DFS را روی گرافی که یالهای آنرا معکوس کرده ایم به ترتیب نزولی fها اجرا می کنیم. مولفه های همبند قوی بدست می آیند.
مرتبه الگوریتم یافتن مولفه های قوی همان مرتبه DFS است و از مرتبه O(V+E) می باشد.
راه حلتون درست اما ...
چرا این کار رو میکنیم. دلیل برعکس کردن جهات، نزولی f ها چیه؟
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به 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 |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close